【BZOJ4013】[HNOI2015]实验比较(动态规划)

时间:2024-10-18 11:05:08

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