メモ

yukicoderでゆるふわgolf

yukicoder No.243 出席番号(2)

問題はこちら
No.243 出席番号(2) - yukicoder

出席番号を1ずらして1-based index、すなわち\{1,\ldots,N\}とする。
X=\{1,\ldots,N\}とおく。
\mathcal{P}(X)Xのべき集合、すなわち\mathcal{P}(X)=\{S | S\subset X\}とする。
f:X→\mathbb{N}
f(i)=(iが嫌いな人の数)
とする。
F:\mathcal{P}(X)→\mathbb{N}
F(S)=(「i \in S \Rightarrow iが嫌いな人に出席番号iが割り当てられている」を満たす割り振りの個数)
とする。
定義より、F(S)=(N-|S|)!*\prod_{x\in S}f(x)である。
(Sの元であるようなxは、それが嫌いな誰かに割り当てられているのでf(x)通り。Sの元を全て割り当てた残りの(N-|S|)個は好きなように割り当てられるので(N-|S|)!通り)

包除原理より、求める答えは\sum_{S\in \mathcal{P}(X)}(-1)^{|S|}*F(S)である。
これを変形していく。
\displaystyle {\sum_{S\in \mathcal{P}(X)}(-1)^{|S|}*F(S)\\
=\sum_{S\in \mathcal{P}(X)}(-1)^{|S|}*(N-|S|)!*\prod_{x\in S}f(x)\\
=\sum_{i=0}^{N}\sum_{|S|=i}(-1)^{|S|}*(N-|S|)!*\prod_{x\in S}f(x)\\
=\sum_{i=0}^{N}(-1)^{i}*(N-i)!*\sum_{|S|=i}\prod_{x\in S}f(x)}
ここでdp[k][i]=\displaystyle{\sum_{|S|=i \atop S\subset\{1,\ldots,k\}}\prod_{x\in S}f(x)}とおく。
(ただしk=0のとき\{1,\ldots,k\}空集合を表すとする)

\displaystyle{
dp[k][i]\\
=\sum_{|S|=i \atop S\subset\{1,\ldots,k\}}\prod_{x\in S}f(x)\\
=\sum_{|S|=i \atop S\subset\{1,\ldots,k-1\}}\prod_{x\in S}f(x)+\sum_{|T|=i-1 \atop T\subset\{1,\ldots,k-1\}}f(k)*\prod_{x\in T}f(x)\\
=dp[k-1][i]+dp[k-1][i-1]*f(k)
}
(2行目から3行目への変形は、Sに関する和を、kを含むものと含まないものに分解することにより得られる)
dp[0][0]=1を初期値とするdpにより、dp[N][*]はO(N^2)で求めることができる。
求める答えは
\sum_{i=0}^{N}(-1)^i*(N-i)!*dp[N][i]
だった。

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

ゴルフは後で