[조합 계수] BZOJ4013 [HNOI 2015] 실험 비교

【제목】 BZOJ는 n n n 개의 물품과 m m m 개의 품질 관계(작거나 같음)가 있고 모든 물품은 많게는 관계(즉 어떤 물품보다 품질이 작음)보다 작으며 모든 관계의 품질 서열수를 만족시키려고 한다.n ≤ 100 n\leq 100 n≤100
[문제풀이 사고방식] 제목이 정한 관계가 모든 점을 만족시키고 대부분이 가장자리에 들어가면 합법적인 방안은 반드시 숲이다.같은 점을 모두 합친 다음 점포 트리 DP\text{DP} DP를 만듭니다.
령fi,jf{i, j}fi, j는 ii를 뿌리로 하는 서브트리를 jj의 부등단(j-3-1j-1j-3-1 j-3 1개보다 작은 번호)으로 나누는 방안을 나타낸다. 그러면 이동은 두 개의 길이를 각각 a, ba, ba, b의 서열로 합치는 것이다.분명히 합병 후 길이 ccc는 max⁡(a,b)≤c≤a+b\max(a,b)\leqc\leqa+bmax(a,b)≤c≤a+b를 만족시킨다.fi, c= fv 1, a∗ fv 2, b∗ (c a)∗ (a b--(c --a) f{i,c}=f_{v1,a}*f_{v2,b}*{c\choose a}*{a\choose b-(c-a)} fi,c​=fv1,a​∗fv2,b​∗(ac​)∗(b−(c−a)a​).
이 감의 의미는 먼저 cc의 위치에서 aa를 선택하면 c-3-ac-a는 두 번째 서열의 수를 놓는다는 것이다.이어 b-b개수 중 b-3-(c-3-a)b-(c-a)b-3-(c-3-a)수를 뽑아 aa의 숫자와 통합해야 한다.
복잡도 O (n 3) O (n ^3) O (n 3) 는 매 쌍이 LCA\text {LCA} LCA에서만 DP\text {DP} DP에 도착하기 때문이다.
[코드 참조]

#include
#define mkp make_pair
#define fi first
#define se second
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int N=105,mod=1e9+7;
int n,m,tot,cnt,ans;
int head[N],fa[N],siz[N],du[N],C[N][N],f[N][N],g[N];
pii p[N];

int read()
{
	int ret=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) ret=ret*10+(c^48),c=getchar();
	return ret;
}

struct Tway{int v,nex;}e[N<<1];
void add(int u,int v){e[++tot]=(Tway){v,head[u]};head[u]=tot;}
int findf(int x){return fa[x]==x?x:fa[x]=findf(fa[x]);}

void dfs(int x)
{
	f[x][0]=1;
	for(int i=head[x];i;i=e[i].nex)
	{
		int v=e[i].v;dfs(v);siz[x]+=siz[v];
		for(int j=0;j<=siz[x];++j) for(int k=1;k<=siz[v];++k)
		{
			for(int l=max(j,k);l<=min(n,j+k);++l)
			{
				int now=1ll*C[l][j]*C[j][k-(l-j)]%mod;
				now=1ll*now*f[x][j]%mod*f[v][k-1]%mod;
				g[l]+=now;g[l]%=mod;
			}
		}
		for(int j=0;j<=siz[x];++j) f[x][j]=g[j],g[j]=0;
	}
	++siz[x];
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("BZOJ4013.in","r",stdin);
	freopen("BZOJ4013.out","w",stdout);
#endif
	n=read();m=read();
	for(int i=0;i<=n;++i)
	{
		fa[i]=i;C[i][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<=m;++i)
	{
		int x,y;char ch[2];
		x=read();scanf("%s",ch);y=read();
		if(ch[0]=='=') fa[findf(x)]=findf(y);
		else p[++cnt]=mkp(x,y);
	}
	for(int i=1;i<=cnt;++i) add(findf(p[i].fi),findf(p[i].se)),du[findf(p[i].se)]++;
	cnt=0;
	for(int i=1;i<=n;++i) if(findf(i)==i) 
	{
		if(du[i]==0) add(n+1,i);
		++cnt;
	}
	dfs(n+1);
	for(int i=1;i<=n;++i) ans=(ans+f[n+1][i])%mod;
	printf("%d
",ans);
	return 0;
}