問題はこちら
No.243 出席番号(2) - yukicoder
出席番号を1ずらして1-based index、すなわちとする。
とおく。
をのべき集合、すなわちとする。
を
が嫌いな人の数
とする。
を
(「が嫌いな人に出席番号が割り当てられている」を満たす割り振りの個数
とする。
定義より、である。
(Sの元であるようなxは、それが嫌いな誰かに割り当てられているのでf(x)通り。Sの元を全て割り当てた残りの(N-|S|)個は好きなように割り当てられるので(N-|S|)!通り)
包除原理より、求める答えはである。
これを変形していく。
ここでとおく。
(ただしk=0のときは空集合を表すとする)
(2行目から3行目への変形は、Sに関する和を、kを含むものと含まないものに分解することにより得られる)
dp[0][0]=1を初期値とするdpにより、dp[N][*]はO(N^2)で求めることができる。
求める答えは
だった。
d[k][*]はd[k-1][*]のみから決まるので、更新順序に気を付けて1次元にすることができる
P=1e9+7; f[6000],n,t,ans; long dp[6000],fact[6000]; main(){ fact[0]=1; for(int i=1;i<5010;i++)fact[i]=fact[i-1]*i%P; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&t); f[t]++; } dp[0]=1; for(int k=0;k<n;k++)for(int i=k;i>=0;i--)dp[i+1]=(dp[i+1]+dp[i]*f[k])%P; for(int i=0;i<=n;i++)ans=(ans+(i%2?-1:1)*fact[n-i]*dp[i])%P; printf("%d",(ans+P)%P); }
ゴルフは後で