読者です 読者をやめる 読者になる 読者になる

AOJ 2378: SolveMe

ブログに記事を書きます Advent Calendar 2014 - Adventarに記事を書きたいのに問題を解く暇がないので、過去のをひっぱりだすということにしました。

ということでSolveMe。

X,Y,ZのうちX,Zをまとめられることは自明だと思います。コードで実験して実はX,Y,ZはX-Y+Zというひとつの値によるということがわかります。(X=Y=Z=0のときは例外)(ここらへん数学が強い人はすぐ見えるらしい……)。
X=Y=Z=0のときは、0回しか使わないほうが全単射である必要がないので、これだけは例外です。

この「実験をする」にたどりつくことが本質です。あとはウィニングラン。気合でDPを書きましょう。実装がかなり難しいのでここからでも時間はかかります。

#include<stdio.h>
#include<algorithm>
using namespace std;
long long mod=1000000007;
int inv[1100];
int fact[1100];
int factinv[1100];
int pow[1100][1100];
int factpow[1100][1100];
int invpow[1100][1100];
long long dp[1100][1100];
long long dp2[1100][1100];
long long dp3[1100][1100];
int finvpow[1100][1100];
long long gcd(long long a,long long b){
    while(a){
        b%=a;
        long long c=a;a=b;b=c;
    }
    return b;
}
long long ABS(long long a){return max(a,-a);}
int main(){
    inv[1]=1;
    for(int i=2;i<1100;i++)inv[i]=(mod-(mod/i)*(inv[mod%i])%mod)%mod;
    fact[0]=factinv[0]=1;
    for(int i=1;i<1100;i++){
        fact[i]=(long long)fact[i-1]*i%mod;
        factinv[i]=(long long)factinv[i-1]*inv[i]%mod;
    }
    for(int i=0;i<1100;i++){
        pow[i][0]=factpow[i][0]=invpow[i][0]=finvpow[i][0]=1;
        for(int j=1;j<1100;j++){
            pow[i][j]=(long long)pow[i][j-1]*i%mod;
            factpow[i][j]=(long long)factpow[i][j-1]*fact[i]%mod;
            invpow[i][j]=(long long)invpow[i][j-1]*inv[i]%mod;
            finvpow[i][j]=(long long)finvpow[i][j-1]*factinv[i]%mod;
        }
    }
    int a;
    long long b,c,d;
    scanf("%d%lld%lld%lld",&a,&b,&c,&d);
    long long t=ABS(b-c+d);
    if(b==0&&c==0&&d==0){
        long long ret=0;
        for(int i=0;i*2<=a;i++){
            ret=(ret+(long long)fact[a]*invpow[2][i]%mod*factinv[i]%mod*factinv[a-i*2]%mod)%mod;
        }
        printf("%lld\n",ret*pow[a][a]%mod);
        return 0;
    }
    for(int i=1;i<=a;i++){
        dp3[i][0]=1;
        for(int j=1;j<=a/i;j++){
            if(t%j||gcd(t/j,i)!=1)continue;
            for(int k=a/i;k>=0;k--){
                for(int l=1;k+l*j<=a/i;l++){
                    dp3[i][k+l*j]=(dp3[i][k+l*j]+(long long)dp3[i][k]*finvpow[j][l]%mod*factinv[l]%mod*factpow[j-1][l]%mod*invpow[i][l])%mod;
                }
            }
        }
    }
    for(int i=1;i<=a;i++){
        if(i%2==0){
            for(int j=0;j<=a/i;j++){
                if(j%2)continue;
                dp2[i][j]=(long long)fact[i*j]*factinv[j/2]%mod*invpow[2][j/2]%mod*finvpow[i][j]%mod*pow[i][j/2]%mod;
            }
            continue;
        }
        for(int j=0;j<=a/i;j++){
            for(int k=0;k*2<=j;k++){
                dp2[i][j]=(dp2[i][j]+(long long)fact[i*j]*factinv[j-k*2]%mod*factinv[k]%mod*invpow[2][k]%mod*pow[i][k]%mod*finvpow[i][j])%mod;
            }
        }
    }
    dp[0][0]=1;
    for(int i=0;i<=a;i++){
        for(int j=0;j<a;j++){
            if(!dp[i][j])continue;
            int v=j+1;
            for(int k=0;i+k<=a;k+=v){
                dp[i+k][v]=(dp[i+k][v]+(long long)dp[i][j]*dp2[v][k/v]%mod*dp3[v][k/v]%mod*fact[k/v]%mod*factpow[v][k/v]%mod*fact[a-i]%mod*factinv[a-i-k]%mod*factinv[k])%mod;
            }
        }
    }
/*  for(int i=1;i<=a;i++){
        for(int j=0;j<=a/i;j++){
            printf("%lld ",dp2[i][j]*dp3[i][j]%mod*fact[j]%mod*factpow[i][j]%mod);
        }
        printf("\n");
    }
    for(int i=0;i<=a;i++){
        for(int j=0;j<=a;j++)printf("%lld ",dp[j][i]);
        printf("\n");
    }*/
    printf("%lld\n",dp[a][a]%mod);
}