题目链接:http://poj.org/problem?id=3070
解题思路:
矩阵二分幂c;模板题~~~~~水过
代码如下:
<code class="tags" href="/tags/CLASS.html" title=class>class="language-cpp">#include<iostream> #include<cstring> #include<cmath> #include<cstdio> #include<algorithm> #include<climits> using namespace std; #define CLR(arr, what) memset(arr, what, sizeof(arr)) typedef long long LL; const LL Size = 2; const LL MOD = 10000; //取余 class="tags" href="/tags/CLASS.html" title=class>class Matrix67 { public: Matrix67(const LL ff1, const LL ff2, const LL aa, const LL bb, const LL cc, const LL nn); //构造函数 void copymat(LL mata[Size][Size], LL matb[Size][Size]); //矩阵复制:后->前 void binary(LL n); //矩阵二分幂:次数 void multiply(LL mata[Size][Size], LL matb[Size][Size]); //矩阵连乘 void put(LL mata[Size][Size]); //调试~ LL result(); //打印结果 private: LL f1, f2, a, b, c, n; LL mat[Size][Size], temp[Size][Size], mid[Size][Size]; //二分幂、递推、单位矩阵 }; void Matrix67::put(LL mata[Size][Size]) { cout<<endl; for(int i = 0; i < Size; ++i) { for(int j = 0; j < Size; ++j) cout<<mata[i][j]; cout<<endl; } cout<<endl; } Matrix67::Matrix67(const LL ff1, const LL ff2, const LL aa, const LL bb, const LL cc, const LL nn) { CLR(mat, 0); CLR(temp, 0); CLR(mid, 0); f1 = ff1, f2 = ff2, a = aa, b = bb, c = cc, n = nn; mat[0][1] = 1, mat[1][0] = 1, mat[1][1] = 1; //初始化单位矩阵 temp[0][0] = ff1, temp[0][1] = ff2; //初始化递推矩阵 copymat(mid, mat); } void Matrix67::copymat(LL mata[Size][Size], LL matb[Size][Size]) { for(int i = 0; i < Size; ++i) for(int j = 0; j < Size; ++j) mata[i][j] = matb[i][j]; } void Matrix67::binary(LL n) { if(n == 1) return ; binary(n >> 1); multiply(mat, mat); if(n & 1) //奇次幂 multiply(mat, mid); } void Matrix67::multiply(LL mata[Size][Size], LL matb[Size][Size]) { LL sum, tempmat[Size][Size]; for(int i = 0; i < Size; ++i) { for(int j = 0; j < Size; ++j) { sum = 0; for(int k = 0; k < Size; ++k) sum = (sum + mata[i][k] * matb[k][j]) % MOD; tempmat[i][j] = (sum + MOD) % MOD; } } copymat(mata, tempmat); } LL Matrix67::result() { if(n == 0) return temp[0][0]; if(n > 1) { binary(n - 1); multiply(temp, mat); } return (temp[0][1] % MOD + MOD) % MOD; } int main() { LL a, b, n; while(scanf("%lld", &n) && n != -1) { Matrix67 m(0, 1, 1, 1, 0, n); printf("%lld\n",m.result() % MOD); } return 0; }code>