AOJ 2611: Ordering

計算量の解析が難しそうだがたぶん例のLCAテクでO(N^2)になるやつのそれぞれでO(N)かかってるからO(N^3)になるんだろうな～と予想がつく。

コンビネーションで上手く数えるだけ。

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int mod=1000000007;
int C[1100][1100];
vector<int>g[1100];
int sz[1100];
int in[1100];
long long dp[1100][1100];
long long dp2[210][210];
void solve(int a){
	sz[a]++;
	for(int i=0;i<g[a].size();i++){
		solve(g[a][i]);
		sz[a]+=sz[g[a][i]];
	}
	for(int i=0;i<210;i++)for(int j=0;j<210;j++)dp2[i][j]=0;
	dp2[0][0]=1;
	int now=0;
	for(int i=0;i<g[a].size();i++){
		for(int j=0;j<=now;j++){
			for(int k=1;k<=sz[g[a][i]];k++){
				for(int l=max(j,k);l<=j+k;l++){
					dp2[i+1][l]=(dp2[i+1][l]+dp2[i][j]*dp[g[a][i]][k]%mod*C[j][k-(l-j)]%mod*C[l][l-j])%mod;
				}
			}
		}
		now+=sz[g[a][i]];
	}
	for(int i=0;i<=now;i++)dp[a][i+1]=dp2[g[a].size()][i];
	//printf("%d: ",a);
	//for(int i=0;i<=now;i++)printf("%lld ",dp[a][i+1]);
	//printf("\n");
}
int main(){
	C[0][0]=1;
	for(int i=0;i<1050;i++){
		for(int j=0;j<=i;j++){
			C[i+1][j+1]=(C[i+1][j+1]+C[i][j])%mod;
			C[i+1][j]=(C[i+1][j]+C[i][j])%mod;
		}
	}
	int a;scanf("%d",&a);
	for(int i=0;i<a-1;i++){
		int p,q;scanf("%d%d",&p,&q);
		g[p].push_back(q);
		in[q]++;
	}
	for(int i=0;i<a;i++){
		if(!in[i]){
			solve(i);
			long long ret=0;
			for(int j=0;j<210;j++)ret=(ret+dp[i][j])%mod;
			printf("%lld\n",ret);
		}
	}
}