[luoguP2461] [SDOI2008]递归数列（DP + 矩阵优化）

传送门

本题主要是构造矩阵，我们只需要把那一段式子看成两个前缀和相减， 然后就直接矩阵连乘。

直接对那个k+1阶矩阵快速幂即可，注意初始化矩阵为单位矩阵，即主对角线（左上到右下）都为1其他都为0。

另外，很多量要开long long。

#include <cstdio> #include <cstring> #define LL long long int k; LL b[21], c[21], n, m, p; struct Matrix }sum, sum1, sum2, t; inline Matrix operator * (Matrix x, Matrix y) inline Matrix operator ^ (Matrix x, LL y) return ans; } int main() if(n k > 0) sum1 = (sum ^ (n k)) * t; else for(i = 1; i <= n; i++) sum1.a[1][1] = (sum1.a[1][1] + b[i]) % p; if(m k 1 > 0) sum2 = (sum ^ (m k 1)) * t; else for(i = 1; i < m; i++) sum2.a[1][1] = (sum2.a[1][1] + b[i]) % p; printf("%lld\n", ((sum1.a[1][1] sum2.a[1][1]) % p + p) % p); return 0; }

　　

上一篇：【模板】manacher算法

下一篇：[luoguP1783] 海滩防御（二分 || 最短路 || 最小生成树）

---

DP 矩阵