http://acm.hdu.edu.cn/showproblem.php?pid=4291
找循环节 + 矩阵连乘
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <vector> #include <algorithm> #define LL long long //#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const LL MOD=1000000007; const LL K1=222222224; const LL K2=183120; LL a[2][2]; LL ans[2]; void Renew(LL M) { LL temp[2]; temp[0]=(ans[0]*a[0][0])%M+(ans[1]*a[1][0])%M; temp[1]=(ans[0]*a[0][1])%M+(ans[1]*a[1][1])%M; ans[0]=temp[0]%M; ans[1]=temp[1]%M; } void Kmul(LL M) { LL temp[2][2]; temp[0][0]=(a[0][0]*a[0][0])%M+(a[0][1]*a[1][0])%M; temp[0][1]=(a[0][0]*a[0][1])%M+(a[0][1]*a[1][1])%M; temp[1][0]=(a[1][0]*a[0][0])%M+(a[1][1]*a[1][0])%M; temp[1][1]=(a[1][0]*a[0][1])%M+(a[1][1]*a[1][1])%M; a[0][0]=temp[0][0]%M;a[0][1]=temp[0][1]%M; a[1][0]=temp[1][0]%M;a[1][1]=temp[1][1]%M; } LL Save(LL n,int M) { a[0][0]=3;a[0][1]=1; a[1][0]=1;a[1][1]=0; ans[0]=1;ans[1]=0; while(n) { if(n&1) { Renew(M); } Kmul(M); n=n>>1; } n=ans[1]; return n; } int main() { //freopen("data.txt","r",stdin); LL n; while(cin>>n) { cout<<Save(Save(Save(n,K2),K1),MOD)<<endl; } return 0; }