这里就不写思路了，想看思路我有一篇转载的矩阵快速幂，下面直接附上模板
#include<stdio.h> #include<string.h> const int N = 2; struct node { int m[N][N]; }; struct node ax(node a, node b, int c) //矩阵乘法 { node temp; memset(temp.m, 0, sizeof(temp.m)); for(int i = 0 ; i < N; i++) for(int j = 0; j < N; j++) for(int k = 0; k < N; k++) { temp.m[i][j] += (a.m[i][k]*b.m[k][j])%c; temp.m[i][j] %= c; } return temp; } struct node ksm(node a, int b, int c) //矩阵快速幂 { node ans; for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) { if(i==j) ans.m[i][j] = 1; else ans.m[i][j] = 0; } while(b) { if(b%2 == 1) ans = ax(ans, a, c); b /= 2; a = ax(a, a, c); } return ans; } int main() { int n; while(~scanf("%d", &n) && n != -1) { if(n <= 1) printf("%d\n", n); else { node a; a.m[0][0] = 1, a.m[0][1] = 1, a.m[1][0] = 1, a.m[1][1] = 0;//递推矩阵 node ans = ksm(a, n, 10000); printf("%d\n", ans.m[0][1]); } } return 0; }