?
题目居然没给描述，我特么真无语了。。。好吧我来发个题目描述：
给出a,c,g,mod,x0,n,xn=(a*xn-1+c)%mod,求xn%g
联想用矩阵快速幂在logn的复杂度下求斐波那契数列，对这题我们也可以采取类似的方法。
我们用矩阵运算来改装这个递推式：
?
设
?
那么
于是可以直接用矩阵快速幂求A矩阵的n次方，然后再乘上x0即可得出xn
此题还有两个坑点：
1、xn求出后，先要mod m，再mod g
2、中间运算过程可能爆long long int，所以最好写个类似于取模快速幂的取模快速乘。
代码：
?
#include#include #include #include #include #define MAXN 3 using namespace std; typedef unsigned long long int LL; LL mod,a,c,x0,n,g; struct matrix { int n,m; LL p[MAXN][MAXN]; }; LL fastmul(LL x,LL y) //快速乘x*y { LL ans=0; while(y) { if(y&1) ans+=x,ans=(ans>mod?ans-mod:ans); x+=x; x=(x>mod?x-mod:x); y>>=1; } return ans; } matrix operator*(matrix a,matrix b) { matrix c; c.n=a.n; c.m=b.m; for(int i=1;i<=a.n;i++) for(int j=1;j<=b.m;j++) { c.p[i][j]=0; for(int k=1;k<=a.m;k++) c.p[i][j]=(c.p[i][j]+(fastmul(a.p[i][k],b.p[k][j]))%mod)%mod; } return c; } matrix fastPow(matrix base,LL pow) { matrix tmp=base,ans; memset(ans.p,0,sizeof(ans.p)); for(int i=1;i<=2;i++) ans.p[i][i]=1; ans.n=ans.m=2; while(pow>0) { if(pow&1) ans=ans*tmp; tmp=tmp*tmp; pow>>=1; } return ans; } int main() { scanf(%llu%llu%llu%llu%llu%llu,&mod,&a,&c,&x0,&n,&g); matrix x,y; x.n=x.m=y.n=y.m=2; x.p[1][1]=a%mod; x.p[1][2]=0; x.p[2][1]=c%mod; x.p[2][2]=1; matrix ans=fastPow(x,n); LL xn=fastmul(ans.p[1][1],x0)+ans.p[2][1]; printf(%llu ,(xn%mod)%g); return 0; }
?
??