NOIP2018 填数游戏

link

Wearry的题解

$O(n+m)$算法实现（为了更好的阅读体验前面的板子删掉了）：

const int p=1000000007;
int fpm(int a,int b){
    int c=1;
    for(;b;b>>=1,a=a*a%p)if(b&1)c=c*a%p;
    return c;
}
int f[1000005][2];
signed main(){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    int n,m;
    read(n,m);
    if(n>m)swap(n,m);
    if(n==1) return write(fpm(2,m),'\n');
    if(n==2)return write(4*fpm(3,m-1)%p,'\n');
    if(n==3 && m==3)return write("112\n");
    int ans=4*
        fpm(4,n-2)%p*fpm(3,m-n)%p*fpm(2,n-1)%p;
    
    if(n==3)
        ans=(ans+4*4*fpm(3,m-4)%p*fpm(2,n-1))%p;
    else
        ans=(ans+4*5*fpm(4,n-4)%p*fpm(3,m-n)%p*fpm(2,n-1))%p;
    f[3][0]=1;
    for(int i=4;i<=m;++i){
        f[i][0]=f[i-1][0];
        if(i<=n){
            f[i][1]=(f[i-1][1]*4+f[i-2][0]*20)%p;
        }
        else if(i==n+1){
            f[i][1]=(f[i-1][1]*3+f[i-2][0]*16)%p;
        }
        else 
            f[i][1]=(f[i-1][1]*3+f[i-2][0]*12)%p;
    }
    if(n==m)
        ans=(ans+4*(f[n][0]*3+f[n][1]*2+f[n-1][0]*12)%p*fpm(2,n-2))%p;
    else
    ans=(ans+2*
            ((f[n][0]*4+f[n][1]*3+f[n-1][0]*16)*fpm(3,m-n-1)%p*fpm(2,n-1)+
             (f[m][0]*3+f[m][1]*2+f[m-1][0]*9)*fpm(2,n-2))%p
            )%p;
    write(ans,'\n');
    return 0;
}

$O(\log n+\log m)$:
（注意到$f_{n,0}=[n\ge 3]$，然后就可以快速幂加速了）

const int p=1000000007,i3=333333336,i2=500000004;
int fpm(int a,int b){
    int c=1;
    for(;b;b>>=1,a=a*a%p)if(b&1)c=c*a%p;
    return c;
}
signed main(){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    int n,m;
    read(n,m);
    if(n>m)swap(n,m);
    if(n==1) return write(fpm(2,m),'\n');
    if(n==2)return write(4*fpm(3,m-1)%p,'\n');
    if(n==3 && m==3)return write("112\n");
    int ans=4*
        fpm(4,n-2)%p*fpm(3,m-n)%p*fpm(2,n-1)%p;
    
    if(n==3)
        ans=(ans+4*4*fpm(3,m-4)%p*fpm(2,n-1))%p;
    else
        ans=(ans+4*5*fpm(4,n-4)%p*fpm(3,m-n)%p*fpm(2,n-1))%p;
    
    int fn=n==3?0:(fpm(4,n-4)-1)*i3%p*20%p;
    if(n==m)
        ans=(ans+4*(3+fn*2+(n>3)*12)%p*fpm(2,n-2))%p;
    else{
        int fm=(fn*3+(n>3)*16),w=fpm(3,m-n-1);
        fm=(fm*w+12*(w-1)%p*i2)%p;
        ans=(ans+2*
            ((4+fn*3+(n>3)*16)*fpm(3,m-n-1)%p*fpm(2,n-1)+
             (3+fm*2+(m>3)*9)*fpm(2,n-2))%p
            )%p;
    }
    write(ans,'\n');
    return 0;
}