, Huang, Jinsong题目链接：?id=3233题目大意：就是求S = A + A2 +A3 + … +Ak咯题目分析：分析可以得到k为偶数：sum(k) = (1+A^(k/2)) *( A+A^2+……+A^(k/2)) = (1+A^(k/2)) * sum(k/2)k为奇数：sum(k) = (1+A^((k-1)/2)) * sum(k/2) + A^k#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int n, m;struct matrix{int m[55][55];}a;matrix multiply(matrix x, matrix y){matrix ans;memset(ans.m, 0, sizeof(ans.m));for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)if(x.m[i][j])for(int k = 1; k <= n; k++)ans.m[i][k] = (ans.m[i][k] + x.m[i][j] * y.m[j][k]) % m;return ans;}matrix add(matrix x, matrix y){for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)x.m[i][j] = (x.m[i][j] + y.m[i][j]) % m;return x;}matrix quickmod(matrix a, int p){matrix ans;memset(ans.m, 0, sizeof(ans.m));for(int i = 1; i <= n; i++)ans.m[i][i] = 1;while(p){if(p & 1)ans = multiply(ans, a);p >>= 1;a = multiply(a, a);}return ans;}matrix solve(matrix a, int k){if(k == 1)return a;matrix ans;memset(ans.m, 0, sizeof(ans.m));for(int i = 1; i <= n; i++)ans.m[i][i] = 1;ans = add(ans, quickmod(a, k >> 1));ans = multiply(ans, solve(a, k >> 1));if(k & 1) //奇数ans = add(ans, quickmod(a, k));return ans;}int main(){int k;scanf("%d %d %d", &n, &k, &m);matrix ans, a;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)scanf("%d", &a.m[i][j]);ans = solve(a, k);for(int i = 1; i <= n; i++){for(int j = 1; j < n; j++)printf("%d ", ans.m[i][j]);printf("%d\n",ans.m[i][n]);}}
，怕仍是不能。于是他们比任何人都看的清楚，又比任何人都看的不确切。
