noi2012 随机数生成器

#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
typedef long long ll;
typedef struct{
    ll dat[3][3];
    int r,c;
}Mat;
ll M,A,C,x0,n,G;
Mat mid,tmp;
ll (ll a,ll b){
    ll res=0;
    while(b){
        if(b&1)res=(res+a)%M;
        a=(a+a)%M;b>>=1;
    }
    return res;
} 
void mul(Mat &a,Mat &b,Mat *to){
    to->r=a.r,to->c=b.c;
    int i,j,k;ll t;
    for(i=0;i<a.r;i++)
        for(j=0;j<b.c;j++){
            t=0;for(k=0;k<a.c;k++)t+=mulll(a.dat[i][k],b.dat[k][j]),t%=M;
            to->dat[i][j]=t%M;
        }
}Mat pow(Mat a,ll p){
    Mat E,F;
    E.r=E.c=a.c;
    int i,j;
    for(i=0;i<a.c;i++)
        for(j=0;j<a.c;j++)
            E.dat[i][j]=(i==j)?1:0;
    while(p){
        if(p&1)mul(E,a,&F),E=F;
        mul(a,a,&F),a=F;p>>=1;
    }return E;
}
int main(){
    scanf("%lld%lld%lld%lld%lld%lld",&M,&A,&C,&x0,&n,&G);
    Mat fib,d,u,v;
    fib.r=fib.c=2;
    fib.dat[0][0]=A%M;
    fib.dat[0][1]=fib.dat[1][1]=1;
    fib.dat[1][0]=0;
    u=pow(fib,n);
    d.r=2,d.c=1;
    d.dat[0][0]=x0%M,d.dat[1][0]=C%M;
    mul(u,d,&v);
    printf("%lldn",v.dat[0][0]%G);
    return 0;
}