【bzoj 4013】[HNOI 2015]樹形dp+組合せ数学の実験比較

湖南人はすごい!!!全然考えられないよ!!!まず、タイトルでは「1枚の画像iに対して、Dちゃんはせいぜい1枚の品質がiより悪くない別の画像Kiしか覚えていない」と述べた.だから、これは木か森です.ループがある場合は、解はなく、0を出力します.等しい点を併合して集計し、一つの点としてdpを考慮し、f[i][j]はiをルートとするサブツリーをjセグメントに併合するシナリオ数(同じ点を併合する)を表し、2本の独立したサブツリーuとvを併合してどれだけのシナリオg[i]+=f[u][j]*f[v][k]*C()(jとkを列挙し、max(j,k)<=i<=j+k)はこの2つを併合してどれだけのシナリオがあるかを考慮し、問題はi個の箱、j個の白球、k個の黒球に等しく、各球を1つの箱に入れ、各箱の各色の球が最も多く、各箱が空にならない案数である.まずj個の白球をi個の箱に入れ、i-j個の箱を残し、まず黒球で埋め、残りのk+j-i個の黒球をj個の白球を入れた箱に入れた.合計シナリオ数はC(j,i)*C(k+j-i,j)≠g[i]+=f[u][j]*f[v][k]*C(j,i)*C(k+j-i,j)(max(j,k)<=i<=j+k)実装の詳細を考慮し、各ノードについて、マージするたびに、リュックサックのようにjとkを列挙し、移行可能なiの各ノードを列挙し、それがリーフノードであればf[u][1]=1;
そうでなければ、ルートノードがいずれのノードと等しくなることは不可能であるため、f[u][i]=f[u][i-1]

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<iostream>
#define maxn 410
#define mod 1000000007

using namespace std;

struct yts
{
	int x,y;
}a[maxn];

int head[maxn],to[maxn],next[maxn];
long long f[maxn][maxn],g[maxn];
int fa[maxn];
bool vis[maxn];
long long c[maxn][maxn];
int d[maxn],size[maxn];
int n,m,num,t,M;
char s[5];

void addedge(int x,int y)
{
	num++;to[num]=y;next[num]=head[x];head[x]=num;d[y]++;
}

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

bool dfs(int x,int fa)
{
	vis[x]=1;
	bool flag=0;
	for (int p=head[x];p;p=next[p])
	  if (to[p]!=fa)
	  {
	  	if (vis[to[p]]) return 0;
	  	if (!dfs(to[p],x)) return 0;
	  	if (flag)
	  	{
	  		memset(g,0,sizeof(g));
	  		for (int j=1;j<=size[x];j++)
	  		  for (int k=1;k<=size[to[p]];k++)
	  		    if (f[x][j] && f[to[p]][k])
	  		      for (int i=max(j,k);i<=j+k;i++)
	  		        g[i]=(g[i]+(long long)((f[x][j]*f[to[p]][k]%mod)*c[i][j]%mod)*c[j][k+j-i]%mod)%mod;
	  		size[x]+=size[to[p]];
	  		for (int i=1;i<=size[x];i++) f[x][i]=g[i];
	  	}
	  	else
	  	{
	  		size[x]=size[to[p]];flag=1;
	  		for (int i=1;i<=size[x];i++) f[x][i]=f[to[p]][i];
	  	}
	  }
	if (x)
	{
		size[x]++;
		if (flag) for (int i=size[x];i>=1;i--) f[x][i]=f[x][i-1];
		else f[x][1]=1;
	}
	return 1;
}

int main()
{
	scanf("%d%d",&n,&M);
	c[0][0]=1;
	for (int i=1;i<=100;i++)
	{
		c[i][0]=1;
		for (int j=1;j<=i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
	}
	for (int i=1;i<=n;i++) fa[i]=i;
	for (int i=1;i<=M;i++)
	{
		int x,y;
		scanf("%d%s%d",&x,s,&y);
		if (s[0]=='=')
		{
			int f1=find(x),f2=find(y);
			fa[f1]=f2;
		}
		else
		{
			a[++m].x=x;a[m].y=y;
		}
	}
	for (int i=1;i<=m;i++)
	{
		int f1=find(a[i].x),f2=find(a[i].y);
		addedge(f1,f2);
		if (f1==f2) {printf("0
");return 0;}
	}
	for (int i=1;i<=n;i++) if (!d[find(i)]) addedge(0,find(i));
	if (!dfs(0,-1)) {printf("0
");return 0;}
	for (int i=1;i<=n;i++) if (fa[i]==i && !vis[i]) {printf("0
");return 0;}
	long long ans=0;
	for (int i=1;i<=size[0];i++) ans=(ans+f[0][i])%mod;
	printf("%lld
",ans);
	return 0;
}