问题：
给定一个无向图，\(n\) 个点编号为 \([0,n-1]\)，\(m\) 条边。从 \(s\) 出发，走 \(k\) 条边，其中相邻的两步不能走同一条边，求最后停在终点 \(t\) 的方案数。
放在 noip 模拟赛 T2 还多测卡常 (?)。考场思路，有点冗余，没有什么高妙的方法。
首先把编号变为 \([1,n]\)。
先不考虑重边，考虑朴素 dp。
设 \(f_{u,i}\) 表示从 \(s\) 出发走 \(i\) 条边且符合题目要求，到达 \(u\) 的方案数。初始时 \(f_{s,0}=1\)。
\(f_{u,i}=\sum_{v\in E_u}f_{v,i-1}\)
然后转移 \(k\) 轮，第 \(i\) 轮对每个 \(u\in[1,n]\) 的 \(f_{u,i}\) 进行更新。
显然这个方程是错的，因为出现不符合题目要求的情况，考虑容斥，减去不合法情况。
不合法情况形如从 \(u\) 走到 \(v\) 又从同一条边走回 \(u\)。
假设最后走回 \(u\) 共走了 \(x\) 条边。
从 \(u\) 转移到 \(v\) 对 \(f_{v,x-1}\) 的贡献为 \(f_{u,x-2}\)，而上述方程式将这多出来不合法的 \(f_{u,x-2}\) 又算进 \(f_{u,x}\) 了。
也就是说每有一个 \(u\) 可以转移的点 \(v\)，也就是点 \(u\) 的度数记为 \(d_u\)，\(f_{u,x}\) 都会算多一次 \(f_{u,x-2}\)。
所以我们可以将方程式改为：
\(f_{u,i}=\sum_{v\in E_u}(f_{v,i-1}-f_{u,i-2})=\sum_{v\in E_u}f_{v,i-1}-d_u\cdot f_{u,i-2}\)
但是还是错的，发现答案少了很多。
思考一下，假设有不合法路径 \(s\to \cdots \to v \to u\to v\to u\)。
同样假设最后走回 \(u\) 共走了 \(i\) 条边。
会发现第二次走到 \(v\) 时，\(f_{v,i-1}\) 将从 \(v\to u\to v\) 贡献的不合法方案数 \(f_{v,i-3}\) 给除去了，也就是 \(u\) 并没有将完整的 \(f_{u,i-2}\) 转移给 \(f_{v,i-1}\)。
但是第二次走回 \(u\) 时我们仍然认为 \(f_u\) 给 \(f_v\) 多转移了 \(f_{u,i-2}\)，于是就会多除去 \(f_{v,i-3}\) 的方案数。
然后就到了这题的关键。
如果存在上述多除去了 \(f_{v,i-3}\) 的点那么必然满足 \(t_v<t-2\)，其中 \(t\) 是当前的转移轮数，\(t_i\) 是从 \(s\) 走到 \(i\) 经过的最小边数。
但是其实可以看作所有与 \(u\) 相连的点 \(v\) 都多除去了 \(f_{v,i-3}\) 因为不满足上述条件的点，其 \(f_{v,i-3}\) 必定为 0。
假定经过转移所有 \(f_{v}\) 都不包含 \(v\to u\to v\) 的非法方案。
::::info[?]
因为 \(t_u\) 轮时转移 \(f_v\) 均不包含 \(v\to u\to v\) 的情况。而后按照上述思路可以保证每次转移后所有 \(v\to u\to v\) 的非法贡献在 \(f_v\) 中除去，所以这样假设是可行的。
::::
发现多除去的 \(\sum_{v\in son_u}f_{v,i-3}\) 刚好是 \(f_{u,i-2}\)。
于是转移式变为：
\(f_{u,i}=\sum_{v\in E_u}f_{v,i-1}-d_u\cdot f_{u,i-2}+f_{u,i-2} \\=\sum_{v\in E_u}f_{v,i-1}-(d_u-1)\cdot f_{u,i-2}\)
有了这个转移式做法就显然了，看到 \(k\le 10^9\) 第一反应就是矩阵加速。
还有一点要注意，就是对于起点 \(s\) 的前两次转移要特殊处理，
因为对于除 \(s\) 外的任意点 \(u\)，第二次走到 \(u\) 时必定会出现 \(s\to\cdots\to v\to u\to v\to u\) 也就是上文多除去了 \(f_{u,i-3}\) 的情况。
但第二次走到 \(s\) 时只会出现 \(s\to u\to s\) 所以时不会出现多除去的情况的，也就是
\(f_{s,2}=\sum_{v\in E_s}f_{v,1}-d_s\cdot f_{s,0}=\sum_{v\in E_s}f_{v,1}-d_s\)
仅有当转移轮数 \(\ge 4\) 时才会对起点 \(s\) 出现多除去的情况。所以前两轮对于起点 \(s\) 的转移会有所不同，而后转移式跟其余点相同（第三轮 \(f_{s,1}\) 必定为 0 所以没影响）。
这是没有考虑重边的情况，考虑重边。
变化不大，直接相当于多了一个点转移过来。
\(f_{u,i}=\sum_{v\in E_u}cnt_{u,v} f_{v,i-1}-(d-1)\cdot f_{u,i-2}\)
其中 \(d_u=\sum_{v\in E_u}cnt_{u,v},cnt_{u,v}\) 表示 \(u,v\) 这条边出现了几次，对 \(s\) 特殊转移的方程也相应稍作修改即可。
下面矩阵加速的部分应该就很好推了：
因为要用到前两轮的状态，于是构造转移到第 \(i\) 轮的矩阵：
表示转移到当前轮各个状态的值，初始（ \(i=0\) ）：
仅有 \(f_{s,0}\) 位置上为 1。
每次转移就相当于乘上 \(2n\times 2n\) 的矩阵：
假设当前为第 \(i\) 轮转移。
形式化的，将所有 \(u\in[1,n],(2u-1,2u)\) 的位置置为 1，表示将 \(f_{u,i-1}\) 处置为 \(f_{u,i}\)。
将 \(u\in[1,n],(2u,2u-1)\) 的位置置为 \(1-d_u\) 表示从 \(f_{u,i}\) 除去多余的 \((d_u-1)\cdot f_{u,i-2}\)。
若 \(u,v\) 有边相连，将 \((u,v)\) 与 \((v,u)\) 置为 \(cnt_{u,v}\)，表示将 \(\sum_{v\in son_u}cnt_{u,v}f_{v,i-1}\) 转移到 \(f_{u,i}\)。
因为上面说前两轮转移起点 \(s\) 要特殊处理，所以定义矩阵 \(C\) 为在矩阵 \(B\) 的基础上将 \((2s,2s-1)\) 置为 \(-d_s\)。
最后答案就是：
\(A_k\) 中对应的 \(f_{t,k}\)。
矩阵快速幂优化一下，就可以做到 \(O(n^3\log k)\) 常数较大可以通过本题。
::::info[多组询问的优化]
对于 加强版 的多组询问，可以先预处理 \(B\) 的 \(2^i\) 次幂的矩阵 \(B'_i\)，然后对 \(k-2\) 做二进制拆分，先计算 \(A=A_0\cdot C^2\)，拆出来每一位就是 \(A\cdot B'_i\) 就变为向量乘矩阵的形式，于是单次乘法复杂度降为 \(O(n^2)\) 总复杂度 \(O(qn^2\log k)\)。
::::
呃呃，然后就结束了吧。写的有点丑，不过有了思路手推一遍也不难。