矩阵优化递推的总结(不定期更新，最后更新20140321)
写在前面：
定义矩阵：
struct Matrix{
LL a[MAX_K][MAX_K],n,m;//n行 m列
Matrix(int _n = 0,int _m = 0):n(_n),m(_m){rep(i,1,n)rep(j,1,m) a[i][j]=0;}
void dw(int _n,int _m){n=_n,m=_m;rep(i,1,n)rep(j,1,m) a[i][j]=(i==j?1:0);}
LL& operator ()(int i,int j){return a[i][j];}
void print(){rep(i,1,n) rep(j,1,m) printf("%I64d%c",a[i][j],j==m?'\n':' ');}
};矩阵乘法：
优化递推通常依赖于矩阵乘法运算；然而，在探讨其应用时，请注意以下几点：其一，在寻找通项公式时经常会涉及特征根方程；其二，在这一过程中可以适当忽略对矩阵乘法基本原理的深入讲解。
定义矩阵A，B。
当且仅当A .m==B.n时 矩阵A,B可乘。
A(x,y)*B(y,z)=C(x,z)
其中每一个元素 Cij=Aik*Bkj (1<=k<=y)
矩阵乘法满足结合律与分配律，结合律是矩阵能够优化递推的关键所在。
矩阵优化递推的一般方法：
构建一个N维向量A(1,n)，一个N*N的转移矩阵B(n,n)
A(1,n)*B(n,n)=C(1,n) 我们发现C与A 同阶，C 又能乘B ...就这样一直递推到需要的一项。
但一般先写出A和下一项C ，再来倒推转移矩阵B
矩阵快速幂：
矩阵乘法一次是O(n^3)的，单凭矩阵乘法优化递推是不可行的。
当然，上面说过矩阵乘法满足结合律，我们考虑矩阵快速幂！
比如要得到递推式的第K项，相当于计算 A*B^K=C
BK可以通过矩阵快速幂O(N3logK)算出
Matrix operator *(Matrix a,Matrix b){//矩阵乘法
Matrix res(a.n,b.m);
rep(i,1,a.n) rep(j,1,b.m) rep(k,1,a.m)
(res(i,j)+=a(i,k)*b(k,j))%=MOD;
return res;
}
Matrix operator ^(Matrix a,LL x){//快速幂
Matrix res;res.dw(a.n,a.m);
for (;x;a=a*a,x>>=1)
if (x&1) res=res*a;
return res;
}矩阵的重要性质：
贴吧大神说矩阵也满足费马小定理？（亟待验证）
http://tieba.baidu.com/p/2472273208
几个矩阵优化的大类：
1.求数列第K项
求fibonacci数列(1,1,2,3,5...)第K项
这个应该是矩阵优化最基础的了，大家都会。
令Fi表示fibonacci数列第i项
构造向量 A=(Fi,Fi-1)，他的下一项是C=(Fi+1,Fi)
倒推转移矩阵B A*B=C
初始是(F1,F0).(F2,F1)..都无所谓啦，。
然后计算斐波那契数列第k项时，在公式A*B^K=C中得到相应的数值；通过适当调整初始矩阵的元素值±1等方式来优化计算结果。
这个例子能发现些什么呢，呃。。没什么。。
[Noi2012]随机数生成器
http://www.lydsy.com/JudgeOnline/problem.php?id=2875
简要描述：
给定数列递推式
求数列{X}的第n项 mod g。
数据范围：
当n及X_₀均不超过N时，在m、a及c均为整数值的情况下（其中m为质数值），满足以下关系：
\begin{cases} n \leq N \\ X_₀ \leq N \end{cases}
其中m为一正整数值，
\begin{cases} |m| > 2 \\ |m| = 2 \\ |m| < 2 \end{cases}
这是一个一阶递推，可以尝试多种方法去解决下：
(1)暴力就不说了。。50分。
(2).求通项：
一般来说，在一阶的情况下仍然可以求得通项公式。然而到了二阶情况后使用特征根法可能会导致出现大量无理数系数（如同斐波那契数列）。
a==1 等差数列....不说了。
a!=1用什么不动点法之类的乱搞一下：
(a-1)^(phi(m)-1)
即(a-1)^(φ(m)-1)
这样加上暴力就有80分。
不错。但是不互质怎么办....
(3)矩阵乘法：
递推式里面有常数有系数 就可以这样搞转移矩阵。
边乘边模就行了，完全不用考虑m是不是质数。
By the way, this problem has a clever trick. When m is less than or equal to 10^18, directly multiplying will cause an overflow in a long long variable. Let me explain the fast multiplication method (also known as rapid multiplication), which transforms multiplication into addition for better efficiency. I won't go into detail here.
这大概不是NOI有史以来最水的题。。
另外也不是所有递推用矩阵都是最好的，例如：
[Noi2013]矩阵游戏
http://www.lydsy.com/JudgeOnline/problem.php?id=3240
（虽然我还没写过） <- <>
F[1][1]=1
F[i,j]=aF[i][j-1]+b (j!=1)
F[i,1]=cF[i-1][m]+d (i!=1)
递推式中a,b,c,d都是给定的常数。
请帮她计算一下F(n,m)的具体数值。请注意结果可能会非常庞大，请确保只返回F(n,m)模1, 123456789（此处数字应根据实际情况调整）。
看上去一切都很和谐，但是，真的用矩阵做好做吗？？（什么log10快速幂....）
这题的重点是模的是一个质数！！！！
所以我们只用求出来F[n][m]的通项就可以了！
注意到n,m是巨大无比的，但是我们的MOD是质数啊~
费马小定理 a^(p-1)=1 (%p)
所以我们的a^n = a^(n%(p-1)) (% p)
再用之求逆元....
搞了半天一个快速幂就行了。
为什么呢？如果模不是素数或者是关键的部分不互质的话，则无法求出相应的逆元了。通常会优先考虑矩阵
显然MOD 是一个质数
灵活使用什么Euler定理，什么数论的...我们这些数学蒟蒻..怎么办啊。。
2.求数列前K项和。
上面的都是求数列第K项是多少，还有的题是求数列前K项的和。Sum=F1+F2+...+Fk
其实这个也很简单啦。
还是拿Fibonacci数列说事吧。
把上面那个矩阵加一维，稍稍改进一下就行了。
这是一个普适性极强的求和法。按理说任何数列都能求和吧。
目前遇到的问题通常可分为两类：一种涉及数位动态规划（number digit DP），另一种则通过矩阵快速幂（matrix exponentiation）来解决。面对N <10^18这样的情况，通常涉及数位动态规划或矩阵快速幂优化！解决这类问题的关键在于如何有效地应用矩阵优化方法。
2014年2月28日更新：
贴吧大神说矩阵也满足费马小定理？（亟待验证）
http://tieba.baidu.com/p/2472273208
若该矩阵符合费马小定理，则这一矩阵游戏将会以另一种形式见了（以后有机会再深入探讨）
2014年3月21日更新：
若有多次询问，同一个矩阵矩阵乘的次数特别多，每次暴力乘是O(n^3logk)的。
乘m次就是O(M*N^3logK)
把转移矩阵的2的幂次方预处理出来存一下，每次不要再暴力算。
然后通过使用初始向量与经过预处理得到的幂次方矩阵相乘，从而实现单次查询时间复杂度为O(N² log k)
这样询问M次的复杂度就是O(N^3logK + M*N^2logK)
当M,N很大的时候，效果还是很明显的，比如矩阵来容斥。