BZOJ2875: [Noi2012]随机数生成器

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2875

Solution

矩阵乘法裸题，没看数据范围，贡献了3个wa。。。那个a和c有点大。。。
要用快速乘
要用快速乘
要用快速乘

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define N 3
using namespace std;
struct matrix{
    ll m[N][N];
}a,b,c,d;
ll mod,n,g;
ll qmul(ll a,ll b){
    ll ans=0;
    for (;b;b>>=1,(a+=a)%=mod)
        if (b&1) (ans+=a)%=mod;
    return ans;
}
matrix mul(matrix x,matrix y){
    memset(d.m,0,sizeof d.m);
    for (ll i=1;i<N;i++)
    for (ll j=1;j<N;j++)
    for (ll k=1;k<N;k++)
        (d.m[i][j]+=qmul(x.m[i][k],y.m[k][j]))%=mod;
    return d;
}
int main(){
    scanf("%lld%lld%lld%lld%lld%lld",&mod,&b.m[1][1],&b.m[2][1],&a.m[1][1],&n,&g);
    a.m[1][2]=b.m[2][2]=c.m[1][1]=c.m[2][2]=1;
    for (;n;n>>=1,b=mul(b,b)) 
        if (n&1) c=mul(c,b);
    a=mul(a,c);
    printf("%lld",a.m[1][1]%g);
}