kmjp's blog

競技プログラミング参加記です

yukicoder : No.243 出席番号(2)

最近O(2^N)系の包除原理の苦手意識が消えてきたと思ったけど、O(N^2)な包除原理はやっぱり苦手。
http://yukicoder.me/problems/643

問題

基本設定は(1)と同じ。
今度は条件を満たす割り振り方の組み合わせ数を求めよ。

解法

Editorialを見て解いた。

出席番号iを嫌いな生徒数をf(i)とする。
0~(N-1)の部分集合Sで衝突(出席番号がその番号を望まない生徒に割当たっている)するような組み合わせは、 \displaystyle (N-|S|)! \times \prod_{x \in S} f(x)となるので、これを包除原理の要領で|S|の偶奇に合わせて足し引きする。

Sをまじめに2^N通り列挙する必要はなく、|S|の個数ごとに組み合わせ数を計算していくDPでO(N^2)で解くことができる。

ll mo=1000000007;
int N;
int X[5010];
ll dp[5050];
ll fact[5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	fact[0]=1;
	for(i=1;i<=5000;i++) fact[i]=fact[i-1]*i%mo;
	
	cin>>N;
	FOR(i,N) cin>>x, X[x]++;
	
	dp[0]=1;
	FOR(i,N) for(x=N;x>=0;x--) if(dp[x]) (dp[x+1] += X[i]*dp[x]) %= mo;
	
	ll ret=0;
	FOR(x,N+1) ret += ((x%2)?(-1):1)*dp[x]*fact[N-x]%mo;
	
	cout<<(ret%mo+mo)%mo<<endl;
}

まとめ

終わってみると非常に単純なんだよなぁ。
下手にUnKoderのマラソン問題が頭に浮かんでしまってはまった。
包除原理=O(2^N)のイメージがあったので、最初にアプローチから外してしまったのよね。