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); }