测试地址：随机数生成器
做法：题目都把递推式给出来了，但是n达到了10^18，所以一个一个算肯定爆了，这个时候就要使用矩阵优化，这个递推式弄出状态转移矩阵还是很简单的，这里就不写了。但是还有一个问题，两个10^18数量级的长整数直接乘起来肯定会炸，所以还要写一个高精度......总之各种麻烦，要注意各种细节，一般写错的话都是写这类东西时常犯的错误（比如进位时+=写成=之类的，我会说我也犯错了么），基本上注意了这些东西就可以写出这道题了。
以下是本人代码（洛谷上能过，BZOJ上WA，不明所以，求解释）：
#include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define ll unsigned long long ll n,m,a,c,g,x; struct hd {ll s[41];}; struct matrix { hd a[2][2]; }M[110],N; void hdfix(hd &a) { for(int i=1;i<=40;i++) if (a.s[i]>=10) { a.s[i+1]+=a.s[i]/10; a.s[i]%=10; } } hd change(ll s) { int i=1; hd a; memset(a.s,0,sizeof(a.s)); while(s!=0) { a.s[i]=s; s/=10; i++; } return a; } hd hdplus(hd a,hd b) { hd c; memset(c.s,0,sizeof(c.s)); for(int i=1;i<=40;i++) c.s[i]=a.s[i]+b.s[i]; hdfix(c); return c; } hd hdmult(hd a,hd b) { hd c; memset(c.s,0,sizeof(c.s)); for(int i=1;i<=40;i++) for(int j=1;j<=40;j++) c.s[i+j-1]+=a.s[i]*b.s[j]; hdfix(c); return c; } hd hdmod(hd a,ll s) { ll sum=0; for(int i=40;i>=1;i--) { sum=sum*10+a.s[i]; sum%=s; } return change(sum); } void clear(matrix &A) { A.a[0][0]=change(0); A.a[0][1]=change(0); A.a[1][0]=change(0); A.a[1][1]=change(0); } matrix matmult(matrix A,matrix B) { matrix C; clear(C); for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) for(int k=0;k<=1;k++) C.a[i][j]=hdmod(hdplus(C.a[i][j],hdmult(A.a[i][k],B.a[k][j])),m); return C; } matrix qmult(ll x) { matrix S; clear(S); S.a[0][0]=S.a[1][1]=change(1); int i=0; while(x!=0) { if (x&1) S=matmult(S,M[i]); x>>=1;i++; } return S; } void output(hd s) { bool flag=0; for(int i=40;i>=1;i--) { if (s.s[i]!=0) flag=1; if (flag) printf("%lld",s.s[i]); } } int main() { scanf("%lld%lld%lld%lld%lld%lld",&m,&a,&c,&x,&n,&g); clear(M[0]); M[0].a[0][0]=change(a); M[0].a[0][1]=change(c); M[0].a[1][1]=change(1); for(int i=1;i<=70;i++) M[i]=matmult(M[i-1],M[i-1]); clear(N); N.a[0][0]=change(x); N.a[1][0]=change(1); output(hdmod(matmult(qmult(n),N).a[0][0],g)); return 0; }
