这实际是求Fibonacci数的一个拓展版。我们用一个10*10的二维数组存储要乘的矩阵，然后对矩阵求k-9次方，最后在乘以前10个数，便得到结果。
程序代码：
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int MAXN = 10; int Integer[MAXN]; int k, m, flag; void Power(int u[][MAXN], int v[][MAXN]) { int t1[MAXN][MAXN], t2[MAXN][MAXN]; memcpy(t1, u, sizeof(int) * MAXN * MAXN); memcpy(t2, v, sizeof(int) * MAXN * MAXN); for(int i = 0; i < MAXN; i++) for(int j = 0; j < MAXN; j++){ u[i][j] = 0; for(int k = 0; k < MAXN; k++){ u[i][j] += t1[i][k] * t2[k][j]; u[i][j] %= m; } } } int main() { int Matrix[MAXN][MAXN], nResult[MAXN][MAXN]; int sum; //freopen("input.txt", "r", stdin); while(scanf("%d %d", &k, &m) == 2){ memset(Matrix, 0, sizeof(Matrix)); for(int i = MAXN - 1; i >= 0; i--) scanf("%d", &Matrix[MAXN - 1][i]); if(k < 10){ printf("%d/n", k % m); continue; } for(int i = 0; i < MAXN - 1; i++) Matrix[i][i + 1] = 1; flag = 0; k -= 9; while(k > 0){ if(k & 1){ if(!flag){ memcpy(nResult, Matrix, sizeof(Matrix)); flag = 1; }else Power(nResult, Matrix); } Power(Matrix, Matrix); k>>=1; } sum = 0; for(int i = 0; i < MAXN; i++){ sum += i * nResult[MAXN - 1][i]; sum %= m; } printf("%d/n", sum); } return 0; }
