TopCoder SRM 669 Div1 Medium LineMST、Div2 Hard LineMSTDiv2

本番中だいぶ回りくどい解法を取ってしまい、時間内に解けず。
http://community.topcoder.com/stat?c=problem_statement&pm=14017
http://community.topcoder.com/stat?c=problem_statement&pm=14018

問題

N頂点の完全無向グラフのうち、各辺のコストは1～Lのいずれかの整数であるようなものを考える。
上記グラフ群に含まれる各グラフGに対し、f(G)とはGのMinimum Spanning Treeのうち木の形状が線(すなわち分岐が無く各点の次数が2以下)のものの数を示す。
全Gに対するf(G)の総和を求めよ。

なお、Div2 HardではL==2固定である。

解法

先に各点に0～(N-1)の番号を振り、MSTが0～(N-1)を順につなぐ線であることを仮定しよう。
そのような線を作るグラフの数を求めていく。
なお、そのように線を作る頂点番号の振り方は、始点と終点を逆にした場合を除くとN!/2通りあるので、上記グラフの数を求めた後(N!/2)を掛けて答えればよい。

以下のように状態を置いてDPする。求めたいのはdp[N][L]である。
dp[n][m] := n頂点からなるグラフでそのMSTが1～nの点を順につなげたものになっているもののうち、最小コストがm以下のものの組み合わせ数

dp[n][m]は以下の和である。

• 最小コストが(m-1)以下のものはdp[n][m]にもカウントされるので、dp[n][m-1]。
• n頂点のうち、先頭x個が最小コストm未満であり、後半(n-x)個が最小コストm以下であり、先頭と後半をコストmの辺でつないでいる場合。
  • この時、x番と(x+1)番の頂点はコストmの辺でなければならないが、それ以外(1～x番)と((x+1)～n番)の間の辺はm以上で結んでよい。
  • よってdp[x][m-1] * dp[n-x][m] * pow(L-m+1, x*(n-x)-1)

以下はDiv1 Medium向けのコードだが、L==2固定と考えるとDiv2 Hardも通る。

ll mo=1000000007;
ll dp[205][205];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

class LineMST {
	public:
	ll dodo(int N,int M,int L) {
		if(dp[N][M]>=0) return dp[N][M];
		if(N==1) return 1;
		if(M==0) return 0;
		
		ll ret=dodo(N,M-1,L);
		for(int x=1;x<N;x++) ret += dodo(x,M-1,L)*dodo(N-x,M,L) %mo * modpow(L-M+1,x*(N-x)-1) % mo;
		return dp[N][M] = (ret%mo);
	}
	int count(int N, int L) {
		MINUS(dp);
		ll ret=dodo(N,L,L);
		for(int i=3;i<=N;i++) ret = ret*i%mo;
		return (int)ret;
	}
}

まとめ

終わってみるとシンプルなDP。