HDU 4291 矩阵快速幂 取模循环节

2019-04-14 08:48发布

站内文章 / 模拟电子
12068 0 915
一开始做这题没注意，WA了一发； g(g(g(n)))%(mod=10^9+7) mod是最外层的模，所以我们要求出里面两层的模 #include #include #include #include #include #include #include #include #include #include #include #include #define PI acos(-1) typedef long long ll; using namespace std; const ll INF = 0xffffffff; const ll mod=1e9+7; const ll N=70000; int main() { ll a=3,b=2; for(ll i=1;;i++) { ll t=3*a+b; t%=mod; b=a; a=t; if(a==3&&b==2) { cout< 最后我们得到第二层：222222224 最里层：183120 最后贴上代码： #include #include #include #include #include #include #include #include #include #include #include #include #define PI acos(-1) typedef long long ll; using namespace std; const ll INF = 0xffffffff; //const ll mod=1e9+7; const ll N=70000; ll a[3]={1e9+7,222222224,183120}; struct node { ll num[2][2]; }A; void init() { A.num[0][0]=3;A.num[0][1]=1; A.num[1][0]=1;A.num[1][1]=0; } node mul(node AA,node BB,ll mod) { node C; for(ll i=0;i<2;i++) { for(ll j=0;j<2;j++) { C.num[i][j]=0; for(ll k=0;k<2;k++) { C.num[i][j]+=AA.num[i][k]*BB.num[k][j]; C.num[i][j]%=mod; } } } return C; } ll solve(ll n,ll mod) { if(n==0)return 0; if(n==1)return 1; n=n-1; node B; B.num[0][0]=1;B.num[1][0]=0; while(n>0) { if(n&1)B=mul(A,B,mod); A=mul(A,A,mod); n=n>>1; } return B.num[0][0]; } int main() { ll n; while(cin>>n) { ll result,mod; for(ll i=0;i<3;i++) { init(); mod=a[2-i]; result=solve(n,mod); n=result; } cout<          

热门文章