矩阵快速幂构造技巧解析
矩阵快速幂的核心难点在于构造合适的递推矩阵。这里通过几个典型斐波那契变种问题，展示矩阵构造的通用思路。
基础：斐波那契前n项和
问题链接：AcWing 1756
设 S(n) = F(1) + F(2) + ... + F(n)，目标是快速计算 S(n) mod m。
构造状态向量为 [F(n), F(n-1), S(n)]^T，则递推关系为：
F(n) = 1*F(n-1) + 1*F(n-2) + 0*S(n-1)
F(n-1) = 1*F(n-1) + 0*F(n-2) + 0*S(n-1)
S(n) = 1*F(n-1) + 1*F(n-2) + 1*S(n-1)
对应矩阵 A 为：
[[1, 1, 0],
[1, 0, 0],
[1, 1, 1]]
但上述代码使用了一个不同的技巧：通过二阶递推构造三阶矩阵。其核心矩阵为：
[[2, 0, -1],
[1, 0, 0],
[0, 1, 0]]
初始向量 S = [F(2), F(1), F(0)]^T = [2, 1, 0]^T，经过 n-1 次乘法后得到 [F(n+1), F(n), F(n-1)]^T。
矩阵乘法实现时需要注意缓存问题：
void multi(ll vec[], ll mat[][N]) {
ll temp[N] = {0};
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
temp[i] = (temp[i] + vec[j] * mat[i][j]) % m;
for (int i = 0; i < N; i++)
vec[i] = temp[i];
}
void multi(ll matA[][N], ll matB[][N]) {
ll temp[N][N] = {0};
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
for (int k = 0; k < N; k++)
temp[i][j] = (temp[i][j] + matA[i][k] * matB[k][j]) % m;
memcpy(matA, temp, sizeof(temp));
}
快速幂循环中，向量乘矩阵与矩阵乘矩阵交替进行，最终从向量中提取 F(n) 作为结果。
进阶：加权斐波那契和
问题链接：AcWing 1757
求 T(n) = 1*F(1) + 2*F(2) + ... + n*F(n) mod m。
系数随 n 变化，不能直接静态构造。引入辅助量 P(n) = n*S(n) - T(n)，其中 S(n) = F(1)+...+F(n)。
状态向量设为 [F(n), F(n+1), S(n), P(n+1)]^T，递推关系为：
F(n+1) = 0*F(n) + 1*F(n+1) + 0*S(n) + 0*P(n+1)
F(n+2) = 1*F(n) + 1*F(n+1) + 1*S(n) + 0*P(n+1)
S(n+1) = 0*F(n) + 0*F(n+1) + 1*S(n) + 1*P(n+1)
P(n+2) = 0*F(n) + 0*F(n+1) + 0*S(n) + 1*P(n+1)
对应递推矩阵：
[[0, 1, 0, 0],
[1, 1, 1, 0],
[0, 0, 1, 1],
[0, 0, 0, 1]]
初始向量 [F(1), F(2), S(1), P(2)] = [1, 1, 1, 0]。经过 n-1 次乘法后，从向量中提取 S(n) 和 P(n+1)，计算 T(n) = n*S(n) - P(n+1)。
核心代码：
int mat[4][4] = {
{0, 1, 0, 0},
{1, 1, 1, 0},
{0, 0, 1, 1},
{0, 0, 0, 1}
};
int state[4] = {1, 1, 1, 0};
int k = n - 1;
while (k) {
if (k & 1) mulVec(state, mat);
mulMat(mat, mat);
k >>= 1;
}
// 结果 = n * state[2] - state[3]
构造要点总结
- 状态选择：包含所有递推需要的旧项，以及需要计算的目标项。
- 递推线性化：确保每个新状态都是旧状态的线性组合。
- 差分化技巧：对于系数变化的求和，引入辅助量使递推矩阵固定。
- 缓存保护：矩阵乘法必须使用临时数组，避免原地更新导致数据污染。
