入门级矩阵快速幂，自己打了个属于自己的模板！
View Code 1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 typedef __int64 ll; 8 const int mod = 10000; 9 const int matSize = 100;10 11 struct Matrix {12 ll val[matSize][matSize];13 14 Matrix(bool Init = false) {15 for (int i = 0; i < matSize; i++) {16 for (int j = 0; j < matSize; j++) {17 val[i][j] = 0;18 }19 if (Init) val[i][i] = 1;20 }21 }22 23 24 void print() {25 for (int i = 0; i < matSize; i++) {26 for (int j = 0; j < matSize; j++) {27 printf("%I64d ", val[i][j]);28 }29 puts("");30 }31 puts("~~~");32 }33 } Base;34 35 Matrix operator * (Matrix _a, Matrix _b) {36 Matrix ret = Matrix();37 38 for (int i = 0; i < matSize; i++) {39 for (int k = 0; k < matSize; k++) {40 if (_a.val[i][k]) {41 for (int j = 0; j < matSize; j++) {42 ret.val[i][j] += _a.val[i][k] * _b.val[k][j];43 ret.val[i][j] %= mod;44 }45 }46 }47 }48 49 return ret;50 }51 52 Matrix operator ^ (Matrix _a, ll _p) {53 Matrix ret = Matrix(true);54 55 while (_p) {56 if (_p & 1) {57 ret = ret * _a;58 }59 _a = _a * _a;60 _p >>= 1;61 }62 63 return ret;64 }65 66 void initBase(ll _k = 1, ll _a = 1) {67 Base.val[0][1] = _k;68 Base.val[1][1] = _a;69 Base.val[0][0] = 0;70 Base.val[1][0] = 1;71 }72 73 ll fun(ll _x) {74 Matrix ret = Matrix();75 76 ret.val[0][0] = 0;77 ret.val[0][1] = 1;78 79 ret = ret * (Base ^ _x);80 // ret.print();81 82 return ret.val[0][0];83 }84 85 ll deal(ll _x) {86 return fun(_x);87 }88 89 int main() {90 ll n;91 92 initBase();93 // Base.print();94 while (~scanf("%I64d", &n) && ~n) {95 printf("%I64d\n", deal(n));96 }97 98 return 0;99 }
——wirtten by Lyon