LOJ 1070 - Algebraic Problem(矩阵快速幂)

xiaoxiao2021-02-28  101

题目链接:点击打开链接

题目大意:

告诉你 p= a+b 的值和 q= ab 的值,求 ( a^n+b^n )%2^64,( p,q,n 都是 32 位有符号的数 ) 思路:

a^n+b^n=(a+b)(a^(n-1)+b^(n-1))-(a*b)a^(n-2)+b^(n-2)

如果另Sn=a^n+b^n

就可以求递推式 :Sn=pS(n-1)-q*S(n-2)

即 (S2 S1)*(p  1)^(n-2)=(Sn S(n-2) )

                          -q   0

# include<cstdio> # include<cstring> #include<iostream> #include<algorithm> using namespace std; #define NUM 50 #define MAXN 2 #define LL unsigned long long LL p,q,n; struct Matrix//矩阵的类 { LL a[NUM][NUM]; void init() //将其初始化为单位矩阵 { memset(a,0,sizeof(a)); for(int i=0;i<MAXN;i++) a[i][i]=1; } } A; Matrix mul(Matrix a,Matrix b) //(a*b)%mod 矩阵乘法 { Matrix ans; for(int i=0;i<MAXN;i++) for(int j=0;j<MAXN;j++) { ans.a[i][j]=0; for(int k=0;k<MAXN;k++) ans.a[i][j]+=(a.a[i][k]*b.a[k][j]); //ans.a[i][j]%=mod; } return ans; } Matrix add(Matrix a,Matrix b) //(a+b)%mod //矩阵加法 { int i,j,k; Matrix ans; for(i=0;i<MAXN;i++) for(j=0;j<MAXN;j++) { ans.a[i][j]=a.a[i][j]+b.a[i][j]; //ans.a[i][j]%=mod; } return ans; } Matrix pow(Matrix a,LL n) //(a^n)%mod //矩阵快速幂 { Matrix ans; ans.init(); while(n) { if(n&1)//n&1 ans=mul(ans,a); n/=2; a=mul(a,a); } return ans; } Matrix sum(Matrix a,LL n) //(a+a^2+a^3....+a^n)%mod// 矩阵的幂和 { LL m; Matrix ans,pre; if(n==1) return a; m=n/2; pre=sum(a,m); //[1,n/2] ans=add(pre,mul(pre,pow(a,m))); //ans=[1,n/2]+a^(n/2)*[1,n/2] if(n&1) ans=add(ans,pow(a,n)); //ans=ans+a^n return ans; } void output(Matrix a)//输出矩阵 { for(int i=0;i<MAXN;i++) for(int j=0;j<MAXN;j++) printf("%lld%c",a.a[i][j],j==MAXN-1?'\n':' '); } int main() { Matrix ans,cnt; int t; scanf("%d",&t); LL sum; int cas=1; while(t--) { scanf("%llu%llu%llu",&p,&q,&n); printf("Case %d: ",cas++); if(n==0) { printf("2\n"); continue; } if(n==1) { printf("%llu\n",p); continue; } if(n==2) { sum=(p*p-2*q); printf("%llu\n",sum); continue; } ans.init(); ans.a[0][0]=p; ans.a[0][1]=1; ans.a[1][0]=-q; ans.a[1][1]=0; ans=pow(ans,n-2); //output(ans); printf("%llu\n",((p*p-2*q)*ans.a[0][0]+(p)*ans.a[1][0])); } return 0; }/* 2 10 16 2 7 12 3 */

转载请注明原文地址: https://www.6miu.com/read-25600.html

最新回复(0)