题目链接:https://ac.nowcoder.com/acm/contest/885/B
题意：已知齐次线性式xn=a*xn-1+b*xn-2，已知a，b，x0，x1，求xn，n很大，n<=10.
思路：矩阵快速幂模板题，构造矩阵t:
a b
矩阵ans：
x1
x0
显然ans1=t×ans,ans1为：
x2
x1
那么ansn=t^n*ans，ansn为：
xn+
xn
所以用矩阵快速幂计算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\n",ans.a[1][0]);
return 0;
}