P1397 [NOI2013]矩阵游戏（递推）

P1397 [NOI2013]矩阵游戏

一波化式子，$f[1][m]=a^{m-1}+b\sum_{i=0}^{m-2}a^i$，用快速幂+逆元求等比数列可以做到$logm$

设$v=a^{m-1},k=\sum_{i=0}^{m-2}a^i$

那么$f[1][m]=v+bk$

再对纵列化一波式子，$f[i][m]=f[i-1][m]*vc+bk+vd$

如果你直接上个矩乘可以拿到65的好分数

#include<iostream>

#include<cstdio>

#include<cstring>

#define ri register int

using namespace std;

typedef long long ll;

const ll P=1e9+;

const ll W=1e9;

char q[];

struct bnum{

    ll a[],len;

    bnum(){memset(a,,sizeof(a));len=;}

    void init(){

        scanf("%s",q); int z=; len=;

        for(ri i=strlen(q)-;i>=;--i){

            a[len]+=(q[i]-)*z; z*=;

            if(z==W) z=,++len;

        }

        while(!a[len]&&len) --len;

    }

    ll mod(){

        ll re=;

        for(ri i=;i<=len;++i) re=(re*W+a[i])%P;

        return re;

    }

    void rem1(){

        --a[];

        for(ri i=;a[i]<;++i) a[i]+=W,--a[i+];

        while(!a[len]&&len) --len;

    }

    bnum div2(){

        bnum c; c.len=len; ll x=;

        for(ri i=len;i;--i)

             x=x*W+a[i],c.a[i]=x/,x%=;

        while(!c.a[c.len]&&c.len) --c.len;

        return c;

    }

}n,m;

struct mat{

    ll a[][];

    mat(){memset(a,,sizeof(a));}

    mat operator * (const mat &b) const{

        mat c;

        for(ri i=;i<;++i)

            for(ri j=;j<;++j)

                for(ri k=;k<;++k)

                    c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j]%P)%P;

        return c;

    }

}s,p;

ll Pow(ll x,ll y){

    ll re=;

    for(;y;y>>=,x=x*x%P) if(y&) re=re*x%P;

    return re;

}

ll Pow_b(ll x,bnum y){

    ll re=;

    for(;y.len;y=y.div2(),x=x*x%P) if(y.a[]&) re=re*x%P;

    return re;

}

mat Pow_m(mat x,bnum y){

    mat re; for(ri i=;i<;++i) re.a[i][i]=;

    for(;y.len;y=y.div2(),x=x*x) if(y.a[]&) re=re*x;

    return re;

}

int main(){

    ll a,b,c,d,v,k;

    n.init(); m.init(); n.rem1(); m.rem1();

    scanf("%lld%lld%lld%lld",&a,&b,&c,&d);

    v=Pow_b(a,m);

    if(a>) k=(v-+P)%P*Pow((a-+P)%P,P-)%P;

    else k=m.mod();

    s.a[][]=(b*k+v)%P; s.a[][]=(b*k%P+v*d%P)%P;

    p.a[][]=v*c%P; p.a[][]=p.a[][]=;

    p=Pow_m(p,n); s=s*p;

    printf("%lld",s.a[][]);

    return ;

}

65pts

观察发现，这个矩乘可以再化：

$f[n][m]=(v+bk)(vc)^{n-1}+(bk+vd)\sum_{i=0}^{n-2}(vc)^i$

观察这个式子，复杂度主要在快速幂上，复杂度$O(logn+logm)$

考虑缩小$n,m$

假设存在：$a^n=a^{n-x}\, mod \; p$，$p$为质数

$\therefore a^x=1\, mod \; p$

根据费马小定理，$x=p-1$

$\therefore a^n=a^{n\, mod\, p-1}\, mod \; p$

输入$n,m$时记下它们$mod\, p,p-1$的值，代入式子即可

注意等比数列公比$=1$时需要特判

#include<iostream>

#include<cstdio>

#include<cstring>

#define ri register int

using namespace std;

typedef long long ll;

const ll P=1e9+;

ll a,b,c,d,v,k,n,m,_n,_m,a_,k_,v_;

void init(){

    char c=getchar();

    while(c<''||c>'') c=getchar();

    while(''<=c&&c<=''){

        n=(n*+c-)%P;

        _n=(_n*+c-)%(P-);

        c=getchar();

    }c=getchar();

    while(c<''||c>'') c=getchar();

    while(''<=c&&c<=''){

        m=(m*+c-)%P;

        _m=(_m*+c-)%(P-);

        c=getchar();

    }

}

ll Pow(ll x,ll y){

    ll re=;

    for(;y;y>>=,x=x*x%P) if(y&) re=re*x%P;

    return re;

}

int main(){

    init(); scanf("%lld%lld%lld%lld",&a,&b,&c,&d);

    n=(n-+P)%P; _n=(_n-+P-)%(P-);

    m=(m-+P)%P; _m=(_m-+P-)%(P-);

    v=Pow(a,_m);

    k=a>?(v-+P)*Pow(a-+P,P-)%P:m;

    a_=v*c%P; v_=Pow(a_,_n);

    k_=a_>?(v_-+P)*Pow(a_-+P,P-)%P:n;

    printf("%lld",((v+b*k)%P*v_%P+(b*k+v*d)%P*k_%P)%P);

    return ;

}

巴特西

P1397 [NOI2013]矩阵游戏（递推）

最新文章

热门文章