矩阵乘法

矩阵乘法的定义很简单，比如说S=X*Y，那么就有S[i][j]=sum(X[i][k]*Y[k][j])。

利用矩阵乘法，可以解决一类DP问题。这一类问题的特点是：状态的某一维特别巨大，但是沿着这一维的决策过程是完全重复或者循环的。

比如说这个问题：一个有向图，沿着每条边走过去的时间都为1，问时刻0在在S点，时刻t在T点共有多少种不同的路径（不一定是简单路径）。

很容易想到的思路是DP，设v[i][j]表示时间i时在v顶点的路径数，边界条件是v[0][S]=1，只需求解v[t][T]即可。由于v[i]之与v[i-1]有关，可以很方便地将状态的储存空间压缩从O(nt)为O(n)，但是如果t特别大（比如说1e9）O(n^2*t)的时间还是要TLE的（最一般的状态转移是需要n^2时间的）。这时就可以使用矩阵乘法来优化。

将v[i]这个一维数组想成一个1*n的矩阵，我们会发现v[i+1]=v[i]*M，其中M是有向图的n x n的邻接矩阵。为什么是这样不大好单纯用语言解释，如果你深刻理解了矩阵乘法的意义，再考虑一下前面的问题的状态转移的过程就会明白。所以说我们要求解的v[t]其实就是v[0]*M*M*M…（t个M）。根据矩阵乘法的结合律，它也就是v[0]*M^t。而M^t这个东西是可以利用类似于快速幂取模的方法在O(log t)的时间内计算出来的（把矩阵乘法当作元运算）。这样我们就把上述时间复杂度变成了O(log t * n^3)，在n不太大，而t可能非常大时，这是非常好使的优化。

更多时候问题没有这么简单，比如说图的顶点可能按照某周期禁止到达啊（ZJOI 2005 day1 swamp），也就是说图的邻接矩阵会随着t而变化。但只要它是周期性的，还是可以直接使用矩阵来优化。只是实现时要注意矩阵乘法是不满足交换律的。

示例程序：swamp.cpp
(ZJOI 2005 day1 swamp)