题目描述
f(x)=c^(2x-6)*f(x-1)*f(x-2)*f(x-3),给定n, f(1), f(2), f(3), c,求f(n) mod(1e9+7)
4<=n<=1e18 , 1<=f(1),f(2),f(3),c<=1e9
题解
g(x)=c^x*f(x) g(x)=g(x-1)*g(x-2)*g(x-3)
令g(x)=g(1)^t1*g(2)^t2*g(3)^t3
分别求t1 , t2 , t3 是 三元斐波那契数列
[x2 x3 x4]=[x1 x2 x3]*[0 0 1]
[1 0 1]
[0 1 1]
因为是指数 所以由费马小定理对(1e+7 -1)取模
g(n)=c^n*f(n) 费马小定理求逆元 完了。。
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 const long long mod=1000000000+7; 5 long long n,f1,f2,f3,c; 6 struct hehe{long long m[4][4];}t1,t2,t3,a,tur,he; 7 hehe operator * (hehe &a,hehe &b) 8 {hehe re; memset(re.m,0,sizeof(re.m)); 9 10 for(int i=1;i<=3;i++) 11 for(int j=1;j<=3;j++) 12 for(int k=1;k<=3;k++) 13 {re.m[i][j]=re.m[i][j]+a.m[i][k]%(mod-1)*b.m[k][j]%(mod-1); 14 } 15 return re; 16 } 17 inline long long ksm(long long a,long long p) 18 {long long re=1; 19 while(p) 20 {if(p&1) re=re*a%mod; 21 p>>=1; 22 a=a*a%mod%mod; 23 } 24 return re; 25 } 26 int main() 27 { 28 scanf("%lld %lld %lld %lld %lld",&n,&f1,&f2,&f3,&c); 29 30 f1=f1*c%mod; f2=f2*c%mod*c%mod; f3=f3*c%mod*c%mod*c%mod; 31 he.m[1][1]=he.m[2][2]=he.m[3][3]=1; 32 tur.m[1][3]=tur.m[2][1]=tur.m[2][3]=tur.m[3][2]=tur.m[3][3]=1; 33 34 t1.m[1][1]=1; t2.m[1][2]=1; t3.m[1][3]=1; 35 36 //tur^n-1 *a 37 long long k=n-1; 38 while(k) 39 {if(k&1) {he=he*tur;} 40 k>>=1; 41 tur=tur*tur; 42 } 43 t1=t1*he; t2=t2*he; t3=t3*he; 44 45 46 long long ans=ksm(f1,t1.m[1][1])*ksm(f2,t2.m[1][1])%mod*ksm(f3,t3.m[1][1])%mod,inv=ksm(c,mod-2); // ans=c^n*f[n] 47 printf("%lld",ans*ksm(inv,n)%mod); 48 return 0; 49 }
[矩阵乘法][费马小定理]Product Oriented Recurrence (Codeforces Round #566 Div. 2 E)
原文：https://www.cnblogs.com/YuXiaoze/p/11031828.html