Let fx=c2x−6⋅fx−1⋅fx−2⋅fx−3
You have given integers nn , f1f1 , f2f2 , f3f3 , and cc . Find fnmod(109+7)fnmod(109+7) .
The only line contains five integers nn , f1f1 , f2f2 , f3f3 , and cc (4≤n≤10184≤n≤1018 , 1≤f11≤f1 , f2f2 , f3f3 , c≤109c≤109 ).
Print fnmod(109+7)fnmod(109+7) .
5 1 2 5 3
72900
17 97 41 37 11
317451037
In the first example, f4=90f4=90 , f5=72900f5=72900 .
In the second example, f17≈2.28×1029587f17≈2.28×1029587 .
矩阵快速幂使用来加速加法的运算
而这个题目给的是乘法
所以要看看式子可不可与搞加法的样子
答案可以写成
ans = c的幂 * f1的幂 * f2的幂 * f3的幂
现在要全球的就是四个数的指数
显然是构造矩阵然后快速幂递推吧,然后就1e9+7是个质数
因此所有的指数都可以mod phi(1e9+7)
1 #include"bits/stdc++.h" 2 using namespace std; 3 #define int long long 4 const int N = 5; 5 const int mod = 1e9+7; 6 struct Mat 7 { 8 int a[6][6]; 9 Mat (){memset(a,0,sizeof a);} 10 11 }; 12 13 inline Mat mul(Mat a,Mat b,int mod ) 14 { 15 Mat c; 16 for(int i=1;i<=N;i++) 17 { 18 for(int j=1;j<=N;j++) 19 { 20 for(int k=1;k<=N;k++) 21 { 22 c.a[i][j] +=a. a[i][k]*b.a[k][j]; 23 c.a[i][j] %= mod; 24 } 25 26 27 } 28 }return c; 29 } 30 inline int ksm(int a,int b,int p) 31 { 32 int ans = 1; a%=p; 33 for(;b;b>>=1,a*=a,a%=p)if(b&1)ans*=a,ans%=p; 34 return ans; 35 } 36 int n,f1,f2,f3,c; 37 38 signed main() 39 { 40 Mat base; 41 base.a[1][1]=0; 42 base.a[1][2]=0; 43 base.a[1][3]=0; 44 base.a[1][4]=1; 45 base.a[1][5]=4; 46 47 Mat t; 48 t.a[1][1]=1; t.a[1][2]=1; 49 t.a[2][1]=t.a[2][3]=1; 50 t.a[3][1]=1; 51 t.a[4][1]=-6; t.a[4][4]=t.a[4][5]=1; 52 t.a[5][1]=2,t.a[5][5]=1; 53 54 cin>>n; n-=3; 55 cin>>f1>>f2>>f3>>c; 56 Mat ans; 57 for(int i=1;i<=5;i++)ans.a[i][i]=1; 58 int b=n; 59 60 b=n; 61 for(;b;b>>=1,t=mul(t,t,1e9+6))if(b&1)ans=mul(ans,t,1e9+6); 62 base=mul(base,ans,1e9+6); 63 //cout<<base.a[1][1]; 64 int Ans = ksm(c,base.a[1][1],mod); 65 // cout<<Ans<<endl; 66 memset(t.a,0,sizeof t.a); 67 memset(base.a,0,sizeof base.a); 68 memset(ans.a,0,sizeof ans.a); 69 70 // f1 71 for(int i=1;i<=5;i++)ans.a[i][i]=1; 72 base.a[1][1]=0; 73 base.a[1][2]=0; 74 base.a[1][3]=1; 75 t.a[1][1]=1; t.a[1][2]=1; 76 t.a[2][1]=t.a[2][3]=1; 77 t.a[3][1]=1; 78 b=n; 79 for(;b;b>>=1,t=mul(t,t,1e9+6))if(b&1)ans=mul(ans,t,1e9+6); 80 base=mul(base,ans,1e9+6); 81 Ans *= ksm(f1,base.a[1][1],mod); Ans %= mod; 82 // cout<<base.a[1][1]<<endl; 83 memset(t.a,0,sizeof t.a); 84 memset(base.a,0,sizeof base.a); 85 memset(ans.a,0,sizeof ans.a); 86 87 88 //f2 89 for(int i=1;i<=5;i++)ans.a[i][i]=1; 90 base.a[1][1]=0; 91 base.a[1][2]=1; 92 base.a[1][3]=0; 93 t.a[1][1]=1; t.a[1][2]=1; 94 t.a[2][1]=t.a[2][3]=1; 95 t.a[3][1]=1; 96 b=n; 97 for(;b;b>>=1,t=mul(t,t,1e9+6))if(b&1)ans=mul(ans,t,1e9+6); 98 base=mul(base,ans,1e9+6); 99 Ans *= ksm(f2,base.a[1][1],mod); Ans %= mod; 100 // cout<<base.a[1][1]<<endl; 101 102 memset(t.a,0,sizeof t.a); 103 memset(base.a,0,sizeof base.a); 104 memset(ans.a,0,sizeof ans.a); 105 106 // f3 107 108 for(int i=1;i<=5;i++)ans.a[i][i]=1; 109 base.a[1][1]=1; 110 base.a[1][2]=0; 111 base.a[1][3]=0; 112 t.a[1][1]=1; t.a[1][2]=1; 113 t.a[2][1]=t.a[2][3]=1; 114 t.a[3][1]=1; 115 b=n; 116 for(;b;b>>=1,t=mul(t,t,1e9+6))if(b&1)ans=mul(ans,t,1e9+6); 117 base=mul(base,ans,1e9+6); 118 Ans *= ksm(f3,base.a[1][1],mod); Ans %= mod; 119 // cout<<base.a[1][1]<<endl; 120 121 122 cout<<Ans; 123 124 125 126 127 128 129 130 131 132 }