2019牛客暑期多校训练营(第五场)- B generator 1 (齐次线性递推+矩阵快速幂)
题目链接:https://ac.nowcoder.com/acm/contest/885/B
题意:已知齐次线性式xn=a*xn-1+b*xn-2,已知a,b,x0,x1,求xn,n很大,n<=1010^6.
思路:矩阵快速幂模板题,构造矩阵t:
a b 1 0
矩阵ans:
x1 0 x0 0
显然ans1=t×ans,ans1为:
x2 0 x1 0
那么ansn=t^n*ans,ansn为:
xn+1 0 xn 0
所以用矩阵快速幂计算t^n,n很大,快速幂要用十进制倍增,对每一位的计算不能直接乘,还要用二进制的快速幂,不然会TLE。
最近写代码像中邪了一样,照着别人的代码写总会有个小地方写错,然后找一天的错误,连续几天了。
AC代码:
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; typedef long long LL; LL x0,x1,a,b; int MOD; char s[1000005]; struct Matrix{ LL a[2][2]; Matrix(){memset(a,0,sizeof(a));} Matrix operator * (const Matrix y){ Matrix ret; for(int i=0;i<2;++i) for(int j=0;j<2;++j) for(int k=0;k<2;++k) ret.a[i][j]=(ret.a[i][j]+a[i][k]*y.a[k][j])%MOD; return ret; } void operator = (const Matrix y){ for(int i=0;i<2;++i) for(int j=0;j<2;++j) a[i][j]=y.a[i][j]; } }tmp; Matrix qpow2(Matrix m,int b){ Matrix ret=tmp; ret.a[0][0]=ret.a[1][1]=1; while(b){ if(b&1) ret=ret*m; m=m*m; b>>=1; } return ret; } Matrix qpow10(Matrix m,char *s){ Matrix ret=tmp; ret.a[0][0]=ret.a[1][1]=1; for(int i=strlen(s)-1;i>=0;--i){ int num=s[i]-'0'; ret=ret*qpow2(m,num); m=qpow2(m,10); } return ret; } int main(){ scanf("%lld%lld%lld%lld",&x0,&x1,&a,&b); scanf("%s%d",s,&MOD); Matrix t,ans; t.a[0][0]=a,t.a[0][1]=b,t.a[1][0]=1,t.a[1][1]=0; ans.a[0][0]=x1,ans.a[0][1]=0,ans.a[1][0]=x0,ans.a[1][1]=1; t=qpow10(t,s); ans=t*ans; printf("%lld ",ans.a[1][0]); return 0; }