题解 | #[HNOI2015]实验比较#

思路

• 这是一道综合性比较高的题目，首先对于相同的几个数来说缩成一个点去看就行了，用并查集处理。
• 接着我们对不等式进行建图（这是一个差分约束系统），并且保证没有重边和自环。
• 然后我们要进行一次拓扑排序看图中有没有环，如果有的话答案直接为0。
• 最终的图可以是一个森林，所以我们可以用0作为汇点使其变成一棵树，之后我们就可以进行树上DP。
• 难点来了，下面是dp的一个思路：
  dp[i]表示以i为根的子树答案显然是不够的，考虑第二维表示什么信息，可以处理同一级结点遍历顺序的问题。设dp[i][j]表示以i为根的子树形成的序列有j个连续段的方案，考虑转移如下：
  如果有j段的序列和k段的序列，拼成l段的序列的方案显然是$C_l^j\times C_j^{k+j-l}\mathrm{。}C\_l^j\; \times \; C\_j^\{k+j-l\}。$
  然后向上面的结点转移就得到了转移式：$dp[i][l]+=dp[i][j]\times dp[son][k]\times C_{l-1}^{j-1}\times C_{j-1}^{k-l+j}dp[i][l]+=dp[i][j]\; \times \; dp[son][k]\; \times \; C\_\{l-1\}^\{j-1\}\; \times \; C\_\{j-1\}^\{k-l+j\}$
  复杂度$O(n^3)O(n^3)$

代码

//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=107;
const int mod=1e9+7;

int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}

int n,m,cnt;
int g[N],dp[N][N],C[N][N],sz[N];
int fa[N],id[N],deg[N];
vector<int>G[N];

int find(int x){
	if(fa[x]==x) return x;
	else return fa[x]=find(fa[x]);
}

void init(){
	C[0][0]=1;
	for(int i=1;i<=n;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	}
	for(int i=1;i<=n+1;i++) fa[i]=i;
}

bool topo(){
	queue<int>q;
	q.push(0);
	while(q.size()){
		int fro=q.front();q.pop();
		for(auto to:G[fro]){
			deg[to]--;
			if(!deg[to]) q.push(to);
		}
	}
	for(int i=0;i<=cnt;i++) if(deg[i]) return false;
	return true;
}

void dfs(int x){
	dp[x][1]=sz[x]=1;
	for(auto to:G[x]){
		dfs(to);
		for(int j=1;j<=sz[x];j++){
			for(int k=1;k<=sz[to];k++){
				int lim=max(k+1,j);
				for(int l=lim;l<=k+j;l++){
					g[l]+=dp[x][j]*dp[to][k]%mod*C[l-1][j-1]%mod*C[j-1][k-l+j]%mod;
					g[l]%=mod;
				}
			}
		}
		sz[x]+=sz[to];
		for(int j=1;j<=sz[x];j++) dp[x][j]=g[j],g[j]=0;
	}
}

struct X{
	int u,v;
	char op; 
}s[N];

signed main(){
	cin>>n>>m;
	init();
	for(int i=1;i<=m;i++){
		cin>>s[i].u>>s[i].op>>s[i].v;
		int uf=find(s[i].u),vf=find(s[i].v); 
		if(s[i].op=='=') fa[uf]=vf;
	}
	for(int i=1;i<=n;i++){
		if(i==fa[i]) id[i]=++cnt;
	}
	for(int i=1;i<=m;i++){
		if(s[i].op=='=') continue;
		int uf=id[find(s[i].u)],vf=id[find(s[i].v)];
		if(uf==vf){
			puts("0");
			return 0;
		}
		G[uf].push_back(vf);
		deg[vf]++;
	}
	for(int i=1;i<=cnt;i++) if(!deg[i]) G[0].push_back(i),deg[i]++;
	if(!topo()){
		puts("0");
		return 0;
	}
	dfs(0);
	int ans=0;
	for(int i=1;i<=cnt+1;i++){
		ans=(ans+dp[0][i])%mod;
	}
	cout<<ans<<"\n";
	return 0;
}