这篇文章上次修改于 366 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
ACM程序课算法笔记19——矩阵快速幂
矩阵快速幂是对递推式的一种高效解决方法。
主要的解决问题是类似于斐波那契数列 f(n) = f(n - 1) + f(n - 2) 的使用。
不过我们要先进行矩阵基本运算在代码中的体现。
矩阵运算
struct mat {
LL a[sz][sz];
mat() { memset(a, 0, sizeof a); }
mat operator-(const mat& T) const {
mat res;
for (int i = 0; i < sz; ++i)
for (int j = 0; j < sz; ++j) {
res.a[i][j] = (a[i][j] - T.a[i][j]) % MOD;
}
return res;
}
mat operator+(const mat& T) const {
mat res;
for (int i = 0; i < sz; ++i)
for (int j = 0; j < sz; ++j) {
res.a[i][j] = (a[i][j] + T.a[i][j]) % MOD;
}
return res;
}
mat operator*(const mat& T) const {
mat res;
int r;
for (int i = 0; i < sz; ++i)
for (int k = 0; k < sz; ++k) {
r = a[i][k];
for (int j = 0; j < sz; ++j)
res.a[i][j] += T.a[k][j] * r, res.a[i][j] %= MOD;
}
return res;
}
mat operator^(LL x) const {
mat res, bas;
for (int i = 0; i < sz; ++i) res.a[i][i] = 1;
for (int i = 0; i < sz; ++i)
for (int j = 0; j < sz; ++j) bas.a[i][j] = a[i][j] % MOD;
while (x) {
if (x & 1) res = res * bas;
bas = bas * bas;
x >>= 1;
}
return res;
}
};上面的矩阵乘法运算是优于下面这个的，优于成块空间的优化导致。
mat operator*(const mat& T) const {
mat res;
for (int i = 0; i < sz; ++i)
for (int j = 0; j < sz; ++j)
for (int k = 0; k < sz; ++k) {
res.a[i][j] += mul(a[i][k], T.a[k][j]);
res.a[i][j] %= MOD;
}
return res;
}问题提出
我们希望在代码角度解决类似于斐波那契数列求第n项的问题
可得
求an项的通项公式
递推公式和矩阵思想
对于以上问题，我们就需要使用矩阵的思想，构建以下矩阵
此时，我们可以发现其中的间接矩阵是我们构建的，并且能让式子成立，并且这就是一个矩阵的递推公式，是一个乘积的形式，每项也就变成了幂次这个间接矩阵。
首项 也就是 1 1了。
拆解这个东西我们就可以发现
这是一个构造的实际例子。为了更便于后序的理解和方法总结，以下再给出6个题目尝试去构造。
矩阵构造
练习一
求f(n)，并且其中有以下递推式
构造一
对于本题，f(n)借力于f(n - 3) f(n - 4)，不妨我们将它们都直入于矩阵
矩阵的构造实际上就是为前一项的多个式能够配到后一项。
可以得到以上矩阵式，我们可以发现，为了让f(n)能够顺利的获取到前面的项，我们就保存了它们，并且让它们出现在前一项。
需要注意的是，我们使用了f(n - 2)它看似无用，实际上是为了保证中间能顺利递推下去。
总结为：它需要什么，我们就存什么
练习二
求f(n)，并且其中有以下递推式
构造二
对于本体，引入了一个常数，这无疑干扰和打破了我们原来计算的规律，但是常数终究是常数，按照构造一的结论，因为需要c，我们就把c一起存起来就好了
以上构造式中，最后一行是c的构造，可以发现 0 0 0 1是一种恒定不变的形式，顺利达成。
练习三
求f(n)，并且其中有以下递推式
其中f(1) = 1 f(2) = 2
构造三
该构造的特点就是，引入的常量变成了一个变量，不同于常量，变量是会变化的，因此我们就需要找到这个变量的变化递推式。
以上构造可以发现，如果是变量，就和原来的f(x)一样，只不过这个变量的递推式更加隐蔽，但是变量已经告诉我们了，我们就可以求出变量的递推式。
练习四
有以下递推式
已知a, b 求 f(a) + f(a + 1) + … + f(b - 1) + f(b)的值。
构造四
这下高级了，想让我们求区间和，但是对于区间和来说，我们应当立马联想到前缀和，两个前缀和就可以得到区间和。
好了，这下前缀和成为了我们的目的值，此时不妨引入T(n)代表前0~n的f值的前缀和。
很巧妙的构造，我们引入了前缀和，并且很好的使用了前缀和的构造式
练习五
f(0) = f(1) = 1
f(n) = X * f(n - 1) + Y * f(n - 2)
S(n) 为 A(i)^2的和 i从0~n
构造五
S(n)更加抽象，作为新引入的值，也是我们的目的值，它使用了平方，但实际上我们只要继续抓住规律，写出S(n)的构造式即可轻松解决
就有以下构造
此时我们甚至没有f(n)项，因为我们的目的是S(n)，所以f(n)就是一个工具，为了便于使用，应该更加灵活。
练习六
一个01循环串,长度为L(L<=100)，这个串每秒都会进行一次变换，变换规则是:如果左边是1，则改变自己的状态，否则保持不变。给定初始状态，问n秒以后这个串的状态。
构造六
题目已经是具体化的题目了，先进行抽象化，我们可以得到
建立的构造如下
构造是一件很灵活的事情，不能只拘泥于简单的递推上，要自己构建自己需要的值的构造式，才能得到构造矩阵。
