TopCoder SRM 661 Div2 Hard ColorfulLineGraphsDiv2

Div1の制限を見てびっくりする問題。
http://community.topcoder.com/stat?c=problem_statement&pm=13842

問題

N頂点が横１列に並んでいる。
ここで以下の要領で色つきグラフを作りたい。

• 各頂点はK色のうちいずれかの色で塗る。
• 左からi番目の頂点は、j＜i番の頂点のうち色が異なる点に有向辺を張ってもよい。張らなくても良い。

グラフの形状は何通りあるか。

解法

K≦3と小さいので、K=3の場合について以下説明。
i番目の頂点について、先に色を決めると左側にある異なる色の頂点の数＋１だけ辺の張り方がある。

例えば色を赤青緑とすると、dp[位置][左にある赤点の数][左にある青点の数]=そのような並べ方の組み合わせ数、としてDPしていけばよい。
左にある緑点の数は位置番号から赤点と青点の数を引けば求められるので、状態としてカウントする必要はない。

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

class ColorfulLineGraphsDiv2 {
	public:
	int countWays(int N, int K) {
		int i,x,y;
		ZERO(dp);
		
		if(K==1) return 1;
		else if(K==2) {
			dp[0][1][0]=1;
			dp[0][0][1]=1;
			for(i=1;i<N;i++) {
				FOR(x,i+1) FOR(y,i+1) if(dp[i-1][x][y]) {
					(dp[i][x+1][y] += dp[i-1][x][y]*(y+1))%=mo;
					(dp[i][x][y+1] += dp[i-1][x][y]*(x+1))%=mo;
				}
			}
		}
		else if(K==3) {
			dp[0][1][0]=1;
			dp[0][0][1]=1;
			dp[0][0][0]=1;
			for(i=1;i<N;i++) {
				FOR(x,i+1) FOR(y,i+1) if(dp[i-1][x][y]) {
					int z=i-x-y;
					(dp[i][x+1][y] += dp[i-1][x][y]*(y+z+1))%=mo;
					(dp[i][x][y+1] += dp[i-1][x][y]*(x+z+1))%=mo;
					(dp[i][x][y] += dp[i-1][x][y]*(x+y+1))%=mo;
				}
			}
		}
		
		ll ret=0;
		FOR(x,N+1) FOR(y,N+1) ret+=dp[N-1][x][y];
		return ret%mo;
	}
}

まとめ

ここまでは割と余裕。