hdu4291 A Short problem 矩阵快速幂 求循环节----成都网络赛

A Short problem

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 300 Accepted Submission(s): 110

Problem DescriptionInputOutputSample InputSample OutputSourceRecommend//求循环节#include<iostream>#include<stdio.h>using namespace std;typedef long long LL;const LLMOD = 1000000007LL;int main() { LL f0 = 0, f1 = 1, temp = -1; for (LL i = 1;; i++) { temp = (3 * f1 + f0) % MOD; f0 = f1; f1 = temp; if (f0 == 0 && f1 == 1) { printf("%I64d\n", i); break; } } return 0;}//const LL MOD = 1000000007LL;//222222224//const LL MOD = 222222224LL;//183120//A题代码#include<cstdio>#include<iostream>#include<cstdlib>#include<stdio.h>#include<math.h>#define ll __int64using namespace std;const int MAX = 2;ll mm;typedef struct{ll m[MAX][MAX];} Matrix;Matrix P ={3,1,1,0};Matrix I ={1,0,0,1};Matrix matrixmul(Matrix a,Matrix b){int i,j,k;Matrix c;for (i = 0 ; i < MAX; i++)for (j = 0; j < MAX;j++){c.m[i][j] = 0;for (k = 0; k < MAX; k++)c.m[i][j] += (a.m[i][k] * b.m[k][j]%mm+mm)%mm;c.m[i][j] = (c.m[i][j]%mm+mm)%mm;}return c;}Matrix quickpow(ll n){Matrix m = P, b = I;while (n >= 1){if (n & 1)b = matrixmul(b,m);n = n >> 1;m = matrixmul(m,m);}return b;}int main(){ ll n; while(scanf("%I64d",&n)!=EOF) { if(n==0) { cout<<0<<endl; continue; } else if(n==1) { cout<<1<<endl; continue; } mm=183120; Matrix g=quickpow2(n-1); ll yy=g.m[0][0]; mm=222222224LL; if(yy!=0&&yy!=1) { g=quickpow2(yy-1); yy=g.m[0][0]; } mm=1000000007LL; if(yy!=0&&yy!=1) { g=quickpow2(yy-1); yy=g.m[0][0]%mm; } printf("%I64d\n",yy); }}