Codeforces #290 Div1 D. Fox And Travelling

本番このDPは思い浮かばなかったな。
http://codeforces.com/contest/512/problem/D

問題

N頂点の無向グラフが与えられる。
ここでK日を過ごすことを考える。

各日は1か所の頂点を訪れるが、訪れる頂点は隣接する未訪問頂点が1個以下の頂点でなければならない。
0～Kの各日滞在した場合に、それぞれ可能な訪問順を答えよ。

解法

閉路や、閉路に挟まれた頂点群は訪問できない。
まずそのような頂点群を縮約して1つの頂点と見なそう。

これには次数1以下の頂点を順次取り除いていき、残った頂点群のうちそれぞれ連結頂点群を1つの縮約した頂点と見なす。
次に、各連結成分ごとにDPを行い、x日間の訪問順を重ね合わせていく。
このDPは、間に縮約した訪問不可頂点があるかないかでやりかたが異なる。

• 訪問不可頂点がある場合：
  • 訪問不可頂点は、縮約後は各連結成分内に1個しかない(複数あっても、その間に挟まれた頂点も訪問できないので結局それらは縮約される)
  • その頂点を根とし、木DPで取り除く順番を数え上げる。
• 訪問不可頂点がない場合：
  • 各頂点を値とした場合の木DPを行い、それぞれの木DPで取り除く順番の総和を取る。
  • x日の訪問順を求める場合、木DPの結果をmax(1,頂点数-x)で割る。これは同じパターンを(頂点数-x)ずつ数え上げているため。

あとは各連結成分ごとの木DPの結果を重ね合わせる。

ll mo=1000000009;
int N,M;
int mat[101][101],mat2[101][101];
int in[101], gr[101], gr2[101], root[101];
int NG[101];
ll dp[101][101],tdp[102];

const int CN=201;
ll C[CN][CN];

ll dfs(int cur,int pre,int inloop=0) {
	int num=0,i,j,k,x;
	ZERO(dp[cur]);
	dp[cur][0]=1;
	FOR(x,N) if(mat[cur][x] && x!=pre) {
		int tn=dfs(x,cur);
		for(i=num;i>=0;i--) for(j=tn;j>=1;j--) (dp[cur][i+j] += dp[cur][i]*dp[x][j]%mo*C[i+j][j]) %= mo;
		num += tn;
	}
	num++;
	if(inloop==0) dp[cur][num]=dp[cur][num-1];
	return num;
}

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;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,CN) for(j=0;j<=i;j++) C[i][j]=(j==0||j==i)?1:(C[i-1][j-1]+C[i-1][j])%mo;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		mat[x-1][y-1]=mat[y-1][x-1]=mat2[x-1][y-1]=mat2[y-1][x-1]=1;
		in[x-1]++;
		in[y-1]++;
	}
	
	queue<int> q;
	FOR(i,N) NG[i]=1;
	FOR(i,N) if(in[i]<=1) q.push(i);
	
	while(q.size()) {
		int k=q.front();
		q.pop();
		if(NG[k]==0) continue;
		NG[k]=0;
		FOR(i,N) if(mat[k][i] && NG[i]==1 && --in[i]<=1) q.push(i);
	}
	
	FOR(i,N) FOR(x,N) FOR(y,N) mat2[x][y] |= mat2[x][i]&&mat2[i][y];
	
	FOR(i,N) {
		gr[i]=gr2[i]=i;
		// union find
		FOR(j,N) if(mat2[j][i]) gr[i]=min(gr[i],j);
		// compact cycle
		FOR(j,N) if(mat2[j][i] && NG[i]&&NG[j]) gr2[i]=min(gr2[i],j);
		if(gr2[i]!=i) FOR(j,N) if(mat[i][j]) mat[gr2[i]][j] |= 1, mat[j][gr2[i]] |= 1, mat[i][j]=mat[j][i]=0;
	}
	FOR(i,N) mat[i][i]=0, root[i]=-1;
	FOR(i,N) if(NG[i]) root[gr[i]]=gr2[i];
	
	tdp[0]=1;
	
	FOR(i,N) if(gr[i]==i) {
		ll tdp2[102]={}, tdp3[102]={};
		if(root[i]==-1) {
			FOR(x,N) if(gr[x]==i) {
				y=dfs(x,-1);
				FOR(j,y+1) (tdp2[j]+=dp[x][j])%=mo;
			}
			
			FOR(j,y+1) tdp2[j]=tdp2[j]*modpow(max(1,y-j))%mo;
		}
		else {
			y=dfs(root[i],-1,1);
			FOR(x,y+1) tdp2[x]=dp[root[i]][x];
		}
		FOR(j,y+1) FOR(x,N+1) if(x+j<=N) (tdp3[x+j]+=tdp[x]*tdp2[j]%mo*C[x+j][j])%=mo;
		FOR(j,N+1) tdp[j]=tdp3[j];
		
	}
	
	FOR(i,N+1) cout<<tdp[i]<<endl;
	
}

まとめ

1秒とかかかると思ったら、意外に100msかかってないのよね。
O(N^3)かO(N^4)かかると思ったんだけどな。