TopCoder SRM 548 Div1 Hard KingdomAndCities

TopCoder 動的計画法 グラフ理論 確率・場合の数

問題

n個の都市があり、そのうち0番からm - 1番のm個の都市は特別な都市である。
これらの都市をk本の道で以下の条件を満たすように接続したい。
条件を満たす接続方法をmod 10^9 + 7で求めよ。

  • 一つの道路は異なる二つの都市を結ぶ
  • ひとつの二つの都市のペアに対して、二本以上の道路がその都市を直接結ぶことはない
  • m個の特別な都市の数に接続する道路の本数はちょうど二本である
  • 任意の二つの都市について、直接または間接に道路を通って移動できる。

制約条件

n≦50
0≦m≦2
k≦50

方針

微妙にeditorialが説明不足だったた。


m = 0, 1, 2で場合わけして求める。
まずはm = 0の場合。


rec(n, k)を求めたい。
都市が連結になるという条件を無視すれば、道の選び方は、C[n * (n - 1) / 2][k]通り。
ここから連結でないものの数を引く。


0番の都市とつながっている成分の大きさをa、その成分の辺の数をeとする。
すると、都市の選びかたがC[n - 1][a - 1]通りで、
都市を選んだ後での作りかたがrec(a, e)通りになる。
残りの部分は自由に辺をつないでよいので、C[(n - a) * (n - a - 1) / 2][k - e]通り。


これを全てのa, eについて足し合わせればよい。


m = 1の場合。
特別な都市を除いて考える。
すると、残りが連結成分1個になる場合と2個になる場合にわけられる。
連結成分が1個のときは、rec(n - 1, k - 2)通り。
そこに辺をつなげる方法がC[n - 1][2]通り。


連結成分が2個の場合は、
片方の連結成分の大きさをa個、そこで使われる辺をe本とすると、
都市の選び方がC[n - 1][a - 1]通り、
左側の作り方がrec(a, e)通り、右側の作り方が(n - a, k - e - 2)通り。
そして、辺の接続の仕方がa * (n - a)通り。
これを全てのa, eについて足せばよい。


m = 2の場合。
特別な都市同士がつながっている場合とそうでない場合にわけられる。
（前者の場合がeditorialには書かれていない）


つながっているときは、残りの連結成分が1個か2個になるかで場合わけできる。
つながっていないときは残りの連結成分が1, 2, 3個になるかで場合わけできる。
それぞれ、上でやったような感じでループを回してdpすればよい。

ソースコード

const int mod = (int)1e9 + 7;
ll dp[60][60], C[2500][2500];
ll rec(int n, int k){
	if(n < 0 || k < 0) return 0;
	ll &res = dp[n][k];
	if(res >= 0) return res;
	
	res = C[n * (n - 1) / 2][k];
	for(int a = 1; a < n; a++) for(int e = 0; e <= k; e++){
		ll tmp = C[n - 1][a - 1] * rec(a, e) % mod * C[(n - a) * (n - a - 1) / 2][k - e] % mod;
		res = (res + mod - tmp) % mod;
	}
	return res;
}

class KingdomAndCities {
	public:
	int howMany(int n, int m, int k) {
		memset(dp, -1, sizeof(dp));
		rep(i, 2500) rep(j, i + 1)
			C[i][j] = j == 0 || j == i ? 1 : (C[i - 1][j] + C[i - 1][j - 1]) % mod;
		
		if(m == 0) return rec(n, k);
		if(m == 1){
			ll ans = C[n - 1][2] * rec(n - 1, k - 2) % mod;
			for(int a = 1; a < n - 1; a++) for(int e = 0; e < k - 1; e++){
				ll tmp = C[n - 2][a - 1] * rec(a, e) % mod * rec(n - 1 - a, k - 2 - e) % mod;
				ans += tmp * a * (n - 1 - a) % mod;
			}
			return ans % mod;
		}
		//特別な都市同士がつながっていて、残り連結成分がひとつ
		ll ans = rec(n - 2, k - 3) * (n - 2) * (n - 2) % mod;
		//特別な都市同士がつながっていて、残り連結成分がふたつ
		for(int a = 1; a < n - 2; a++) for(int e = 0; e < k - 2; e++){
			ll tmp = n >= 3 ? C[n - 3][a - 1] : 0;
			tmp = tmp * rec(a, e) % mod * rec(n - 2 - a, k - 3 - e) % mod;
			ans += tmp * a * (n - 2 - a) * 2 % mod;
		}

		//特別な都市同士が離れていて、残り連結成分がひとつ
		if(n >= 2) ans += rec(n - 2, k - 4) * C[n - 2][2] % mod * C[n - 2][2] % mod;
		//特別な都市同士が離れていて、残り連結成分がふたつ
		for(int a = 1; a < n - 2; a++) for(int e = 0; e < k - 3; e++){
			int b = n - 2 - a, f = k - 4 - e;
			ll tmp = n >= 3 ? C[n - 3][a - 1] : 0;
			tmp = tmp * rec(a, e) % mod * rec(b, f) % mod;
			//特別な都市とのつなぎ方
			tmp = tmp * a * b % mod * (a * b + 2 * (C[a][2] + C[b][2])) % mod;
			ans += tmp;
		}
		//特別な都市同士が離れていて、残り連結成分がみっつ
		for(int a = 1; a < n - 3; a++) for(int e = 0; e < k - 3; e++)
		for(int b = 1; b < n - 3; b++) for(int f = 0; f < k - 3; f++){
			int c = n - 2 - a - b, g = k - 4 - e - f;
			if(c <= 0 || g < 0) continue;
			ll tmp = n >= 3 ? C[n - 3][a - 1] : 0;
			tmp *= (n - 3 - a >= 0 ? C[n - 3 - a][b - 1] : 0);
			tmp = tmp % mod * rec(a, e) % mod * rec(b, f) % mod * rec(c, g) % mod;
			//特別な都市とのつなぎ方
			tmp = tmp * a * b * c * (a + b + c) * 2 % mod;
			ans += tmp;
		}
		return ans % mod;
	}
};