题意：
给定$x_0,x_1,a,b,n,mod, x_i=a*x_{i-1}+b*x_{i-2}$ ,求$x_n % mod$
n最大有1e6位
题解：
矩阵快速幂。
巨大的n并不是障碍，写一个十进制的矩阵快速幂就行了。
$ egin{bmatrix}x_n \ x_{n-1} end{bmatrix}=egin{bmatrix}a &b \ 1 &0 end{bmatrix} *egin{bmatrix}x_{n-1} \ x_{n-2} end{bmatrix}=egin{bmatrix}a &b \ 1 &0 end{bmatrix}^{n-1}egin{bmatrix}x_1 \ x_0 end{bmatrix} $
#include<iostream> #include<cstring> #include<cassert> #define LL long long using namespace std; LL mod; struct Mtx{ LL x[2][2]; friend Mtx operator *(const Mtx &a,const Mtx &b){ Mtx c; LL tmp00=a.x[0][0]*b.x[0][0] % mod+a.x[0][1]*b.x[1][0] % mod; LL tmp01=a.x[0][0]*b.x[0][1] % mod+a.x[0][1]*b.x[1][1] % mod; LL tmp10=a.x[1][0]*b.x[0][0] % mod+a.x[1][1]*b.x[1][0] % mod; LL tmp11=a.x[1][0]*b.x[0][1] % mod+a.x[1][1]*b.x[1][1] % mod; assert(tmp00>=0); assert(tmp01>=0); assert(tmp10>=0); assert(tmp11>=0); c.x[0][0]=tmp00 % mod; c.x[0][1]=tmp01 % mod; c.x[1][0]=tmp10 % mod; c.x[1][1]=tmp11 % mod; return c; } friend Mtx operator ^ (Mtx base,int n){ Mtx ans=Mtx(1); while(n){ if(n%2){ ans=ans*base; } base=base*base; n>>=1; } return ans; } Mtx(){} Mtx(int a){ x[0][0]=1; x[1][1]=1; x[0][1]=0; x[1][0]=0; } }; char n[1000006]; int main(){ LL x0,x1,a,b; scanf("%lld %lld %lld %lld",&x0,&x1,&a,&b); scanf("%s",n); scanf("%lld",&mod); int len=strlen(n); int kk=len-1; Mtx ans=Mtx(1); Mtx base; if(len==1){ if(n[0]=='0'){ printf("%lld ",x0%mod); goto E; } if(n[0]=='1'){ printf("%lld ",x1%mod); goto E; } } while(1){ n[kk]--; if(n[kk]<'0'){ n[kk]+=10; kk--; }else break; } // printf("%s ",n); base.x[0][0]=a; base.x[0][1]=b; base.x[1][0]=1; base.x[1][1]=0; for(int i=0;i<len;i++){ ans=ans^10; ans=ans*(base^(n[i]-'0')); } printf("%lld ",(x1*ans.x[0][0]+x0*ans.x[0][1])%mod); E:return 0; }
小贴士：矩阵快速幂，以及一些其他的，比较复杂的，比较套路的东西，一定要封装好，这样在不太损失效率的前提下最大限度的保证了代码的可读性，这是我某次打cf时wa到自闭的教训。
8月6日PS:这种概念叫做DRY原则，全称是Don't repeat yourself.今天刚学到的名词。