TopCoder SRM 614 Div1 Medium CycleColoring

525ptという珍しい配点のMedium。
本番は計算がややこしくて時間切れになってしまった。
http://community.topcoder.com/stat?c=problem_statement&pm=13013

問題

2重の輪で作られたグラフ構造がある。
全体は小さなN個の輪を連結して作られた大きな輪となっている。

個々の小さな輪は、0～(vertexCount[i]-1)番のvertexCount[i]個の頂点を実線で連結した輪である。
大きな輪は、i番目の輪のfromVertex[i]番の点と(i+1)番目の輪のtoVertex[i+1]番の点とを点線で連結した輪である。

以下のルールにより各頂点をK色で塗り分ける。

• 実線でつながれた点同士は異なる色でなければならない。
• 点線でつながれた点同士は同じ色でなければならない。

色の塗り分け方は何通りあるか。

解法

まず小さい輪の中の組み合わせを考える。
i番目の輪のうち、fromVertex[i]番とtoVertex[i-1]番の色を考えると、これらが同じ場合と異なる場合で残りの色の組み合わせが求められる。

• fromVertex[i]==toVertex[i-1]の場合
  • 小さい輪を構成する残り(vertexCount[i]-1)個の頂点列のうち、両端がfromVertex[i]と異なるようにしたい。
  • 条件を満たすP点は以下のような行列により求められる。
  • ベクトルの下側はfromVertex[i]と同じ色、上側は異なる(K-1)色に相当する。
  • 
• fromVertex[i]とtoVertex[i-1]が隣接する場合
  • 小さい輪を構成する残り(vertexCount[i]-2)個の頂点列のうち、片方の端がfromVertex[i]、もう片方の端がtoVertex[i-1]と異なるようにしたい。
  • 条件を満たすP点は以下のような行列により求められる。
  • ベクトルの下側はfromVertex[i]と同じ色、真ん中はtoVertex[i-1]と同じ色、上側は異なる(K-2)色に相当する。
  • 
• それ以外の場合
  • fromVertex[i]とtoVertex[i-1]がもっと離れている場合、両者を同じ色にする場合と異なる色にする場合それぞれ上の2つの行列を使って求められる。

vertexCount[i]は100K以下なので、先に0＜P＜100Kの分値を求めておくとよい。
後は個々の大きな輪のうち点線について、(N-1)番目の点線((N-1)番目と0番をつなぐ線)と同じ色のケースと異なる色のケースを順次DPで求めていけばよい。

ll mo=1000000007;
ll dps[1000010][4],dpd[1000010][4];

class CycleColoring {
	public:
	int countColorings(vector <int> vertexCount, vector <int> fromVertex, vector <int> toVertex, int K) {
		int i,j;
		int N=vertexCount.size();
		
		dps[0][0]=dpd[0][0]=dpd[0][1]=0;
		dps[0][1]=dpd[0][2]=1;
		dps[0][3]=dpd[0][3]=1;
		
		FOR(i,1000000) {
			dps[i+1][3]=dps[i+1][0]=(dps[i][0]*(K-2)+dps[i][1]*(K-1))%mo;
			dps[i+1][1]=(dps[i][0])%mo;
			dpd[i+1][0]=(dpd[i][0]*(K-3)+dpd[i][1]*(K-2)+dpd[i][2]*(K-2))%mo;
			dpd[i+1][1]=(dpd[i][0]+dpd[i][2])%mo;
			dpd[i+1][2]=(dpd[i][0]+dpd[i][1])%mo;
			dpd[i+1][3]=(dpd[i+1][0]+dpd[i+1][2])%mo;
		}
		
		ll sm[51],df[51];
		ZERO(sm);
		ZERO(df);
		sm[0]=K;
		
		FOR(i,N) {
			int t=fromVertex[i]-toVertex[(i+(N-1))%N];
			if(t<0) t+=vertexCount[i];
			
			if(t==0) {
				sm[i+1]=sm[i]*dps[vertexCount[i]-1][3]%mo;
				df[i+1]=df[i]*dps[vertexCount[i]-1][3]%mo;
			}
			else if(t==1 || t==vertexCount[i]-1) {
				df[i+1]=((K-2)*df[i]+(K-1)*sm[i])%mo*dpd[vertexCount[i]-2][3]%mo;
				sm[i+1]=df[i]*dpd[vertexCount[i]-2][3]%mo;
			}
			else {
				int v1=t-1,v2=vertexCount[i]-t-1;
				ll same=dps[v1][3]%mo*dps[v2][3]%mo;
				ll diff=dpd[v1][3]%mo*dpd[v2][3]%mo;
				
				sm[i+1]=(sm[i]*same+df[i]*diff)%mo;
				df[i+1]=(df[i]*same+((K-2)*df[i]+(K-1)*sm[i])%mo*diff)%mo;
			}
		}
		
		return sm[N];
	}
};

まとめ

本番は行列計算をまじめにやろうとして時間切れ。
P<=100Kだし、単なる3変数の漸化式なので単純に100K回漸化式を進めればよかったのね。