Codeforces #315 Div1 B. Symmetric and Transitive

説明文が無駄にややこしい…。
http://codeforces.com/contest/568/problem/B

問題

N個の要素からなる集合Aに対し、関係ρを考える。
ρはA中の２要素の対の集合からなる。
例えばρに要素(x,y) (x,y∈A)が含まれる場合、演算子≡に対し２値関係x≡yを満たす(逆に含まれないならx≠y)とする。

一般的な２値関係には反射律・対象律・推移律を満たすものが多い。

• 反射律：すべてのxに対しx≡xが成り立つ
• 対象律：x≡yならばy≡xも成り立つ
• 推移律：x≡yかつy≡zならばx≡zも成り立つ

Nが与えられたとき、対象律と推移律を満たしつつ、反射律だけ満たさないρの数を答えよ。

解法

問題文にあるとおり、対象律と推移律が成り立つ関係であれば反射律が成り立ちそうである。
しかし、反射律の定義だけは「すべてのx」と書かれていることに注意。
あるA中の要素aがρ中に１度も登場しないならば、対象律と推移律が成り立っても反射律は成り立たない。

よって、この問題は以下のように考えられる。
N個中でN個未満の要素数のみ、たとえばM個(M＜N)をρに登場させるようにする。これらM個は反射律が成り立つ。
後は対象律と推移律が成り立つような関係の組み合わせ数を求めればよい。

M個の頂点の間に辺を張るグラフを考える。このグラフにおいて、(辺がある)と(ρに含まれる)は同値であるとする。
反射率が成り立つということは辺は常に無向辺であり、推移律が成り立つということは連結された頂点同士はクリークを成すことになる。
すなわち、M個の頂点を幾つかの連結しないクリークに分ける分け方に等しい。
これは結局M番目のベル数B(M)に一致する。

M個の選択法も通りあることを考えると、解はとなることがわかる。

int N;
ll mo=1000000007;
ll dp[4040][4040];
ll dp2[4040];

ll combi(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	ll ret=0;
	for(i=0;i<N;i++) {
		dp[i][1]=dp[i][i]=1;
		for(x=2;x<=i-1;x++) dp[i][x]=(dp[i-1][x-1]+dp[i-1][x]*x)%mo;
		for(x=1;x<=max(1,i);x++) dp2[i]+=dp[i][x];
		dp2[i]%=mo;
		(ret+=dp2[i]*combi(N,i))%=mo;
	}
	cout<<ret<<endl;
}

まとめ

同じ解法が必要な問題を、もう少しシンプルな題材で書くのは難しいかなぁ…。