这题在比赛的时候不知道怎么做，后来看了别人的解题报告，才知道公式sn=(a+sqrt(b))^n+(a-sqrt(b))^n;
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<iomanip> 5 #include<cmath> 6 #include<string> 7 using namespace std; 8 struct ma 9 { 10 __int64 a[2][2]; 11 void init() 12 { 13 a[0][0]=a[1][1]=1; 14 a[0][1]=a[1][0]=0; 15 } 16 }; 17 int mod; 18 ma mul(ma a,ma b) 19 { 20 ma ans; 21 int i,j,k; 22 for(i=0;i<2;i++) 23 for(j=0;j<2;j++) 24 { 25 ans.a[i][j]=0; 26 for(k=0;k<2;k++) 27 ans.a[i][j]=(ans.a[i][j]%mod+((a.a[i][k]%mod)*(b.a[k][j]%mod)%mod))%mod; 28 } 29 return ans; 30 } 31 ma pows(ma a,__int64 n) 32 { 33 ma ans; 34 ans.init(); 35 while(n) 36 { 37 if(n&1) 38 ans=mul(ans,a); 39 n>>=1; 40 a=mul(a,a); 41 } 42 return ans; 43 } 44 int main() 45 { 46 int a,b,n; 47 __int64 sum,q,s; 48 while(scanf("%d%d%d%d",&a,&b,&n,&mod)!=EOF) 49 { 50 ma p,ans; 51 s=2*a%mod; 52 p.a[0][0]=s; 53 p.a[0][1]=(b-a*a)%mod; 54 p.a[1][0]=1; 55 p.a[1][1]=0; 56 q=((2*a*a)%mod+2*b%mod)%mod; 57 ans=pows(p,n-1); 58 sum=(((ans.a[1][0]%mod)*(q%mod))%mod+((ans.a[1][1]%mod)*(s%mod)))%mod; 59 if(sum<0) sum=(sum+mod)%mod; 60 printf("%I64d ",sum); 61 } 62 return 0; 63 }