【BZOJ4013】[HNOI2015]实验比较（动态规划）

题面

BZOJ

洛谷

题解

看题目意思就是给你一棵树，连边表示强制顺序关系。然后你要给点染色，在满足顺序关系的情况下，将序列染成若干个颜色，同颜色之间没有顺序关系。求染色方案数。

那么设\(f[i][j]\)表示以\(i\)为根的子树内有\(j\)种颜色，那么每次枚举当前点的子树内的颜色和新加入的子树内的颜色，假设分别是\(j,k\)，假设总颜色是\(i\)。

那么我们现在要求把\(j\)种颜色和\(k\)种颜色合并出\(i\)种颜色的方案数。

那么手下把\(j\)和\(k\)插到一起形成一个\(j+k\)的数列。

首先钦定\(j\)的颜色必须出现，然后把\(k\)给合并进来。

首先是枚举出现的位置，方案数是\(i-1\choose j-1\)，因为第一个位置钦定是根节点。

然后把\(k\)给插入进来，那么等价于要把\(k\)给分成\(j+k-i\)种颜色，那么方案数是\({k-1\choose j+k-i}\)。

#include<iostream>

#include<cstdio>

using namespace std;

#define MAX 105

#define MOD 1000000007

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

struct Line{int v,next;}e[MAX];

int h[MAX],cnt=1;

inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}

int f[MAX];

int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}

int U[MAX],V[MAX],O[MAX];

int g[MAX][MAX],C[MAX][MAX];

int sz[MAX],tmp[MAX];

void dfs(int u)

{

	sz[u]=1;g[u][1]=1;

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;

		dfs(v);

		for(int j=1;j<=sz[u]+sz[v];++j)tmp[j]=0;

		for(int j=1;j<=sz[u]+sz[v];++j)

			for(int k=1;k<=sz[u];++k)

				for(int l=1;l<=sz[v];++l)

				{

					int x=l-j+k;if(x<0)continue;

					tmp[j]=(tmp[j]+1ll*g[u][k]*g[v][l]%MOD*C[j-1][k-1]%MOD*C[k-1][x])%MOD;

				}

		for(int j=1;j<=sz[u]+sz[v];++j)g[u][j]=tmp[j];

		sz[u]+=sz[v];

	}

}

int n,m,ans,fa[MAX];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;++i)f[i]=i;

	for(int i=1;i<=m;++i)

	{

		int u,v;char s[2];

		scanf("%d%s%d",&u,s,&v);

		if(s[0]=='=')f[getf(u)]=getf(v);

		U[i]=u;V[i]=v;O[i]=(s[0]=='<');

	}

	for(int i=1;i<=m;++i)

		if(O[i])

		{

			Add(getf(U[i]),getf(V[i])),fa[getf(V[i])]=getf(U[i]);

			if(getf(U[i])==getf(V[i])){puts("0");return 0;}

		}

	for(int i=1;i<=n;++i)

		if(!fa[i]&&getf(i)==i)Add(0,i);

	if(!h[0]){puts("0");return 0;}

	for(int i=0;i<=n;++i)C[i][0]=1;

	for(int i=1;i<=n;++i)

		for(int j=1;j<=i;++j)

			C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;

	dfs(0);

	for(int i=1;i<=sz[0];++i)ans=(ans+g[0][i])%MOD;

	printf("%d\n",ans);

	return 0;

}