BZOJ 2875 [Noi2012]随机数生成器

题目大意

给你一个公式$F_i = (a \times F_{i-1} + c) \mod m$，已知$F_0$求$F_n \mod g$.

这题首先懵逼一下之后就可以发现可以递推qwq

之后发现n非常大那就矩阵乘法优化一下。

注意因为a,c,g,m都是LL范围的所以没法用符号'×'，所以就只能使用快速乘进行操作。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long n,m,g;
long long mul(long long tx,long long ty)
{
    long long ret=0,tmp=tx;
    for(long long i=0;(1ll<<i)<=ty;++i,tmp=(tmp<<1)%m) if((1ll<<i)&ty) ret=(ret+tmp)%m;
    return ret;
}
struct matrix
{
    long long v[3][3];
    int w,h;
    matrix(int tx,int ty){h=tx,w=ty;memset(v,0,sizeof v);}
    matrix operator*(const matrix &tx)const
    {
        matrix ret(h,tx.w);
        for(int i=1;i<=h;++i)
            for(int j=1;j<=tx.w;++j)
                for(int k=1;k<=w;++k)
                    ret.v[i][j]=(ret.v[i][j]+mul(v[i][k],tx.v[k][j]))%m;
        return ret;
    }
    matrix operator^(long long &tx)const
    {
        matrix ret(w,h),tmp=(*this);
        for(int i=1;i<=h;++i) ret.v[i][i]=1;
        for(int i=0;(1ll<<i)<=tx;i++,tmp=tmp*tmp) if((1ll<<i)&tx) ret=ret*tmp;
        return ret;
    }
}f(1,2),s(2,2);
int main()
{
    scanf("%lld%lld%lld%lld%lld%lld",&m,&s.v[1][1],&f.v[1][2],&f.v[1][1],&n,&g);
    s.v[1][2]=0,s.v[2][1]=1,s.v[2][2]=1;
    s=s^n;
    f=f*s;
    printf("%lld\n",f.v[1][1]%g);
    return 0;
}