自动搬运

查看原文

来自洛谷，原作者为

	λᴉʍ 大家好，我是刚学OI的萌新

搬运于2025-08-24 21:56:29，当前版本为作者最后更新于2019-03-05 20:14:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P4099 [HEOI2013]SAO

贼板子有意思的一个题～～～我（）竟然没看题解

没卡就暂时这题rk1了来写一发题解

有一张连成树的有向图，球拓扑序数量。

树形dp，设$f[i][j]$表示$i$在子树中$i$拓扑序上排名为$j$的方案数。

难就难在转移，现在有两个树$x$和$y$，其中$x$是父亲，$x$的拓扑序小于$y$的，从$f[x][p1],f[y][p2]$转移到$newf[x][p3]$：$x$在原序列中排名$p1$，新序列中$p3$；$y$在原序列中排名$p2$，新序列中$p4$，那么限制是$p3<p4$

那么$x$子树中，$p1$左边的点也一定在$p3$左边（因为是和同一个点$x$比较）

又有限制$p3<p4$，所以$y$的原序列中排名为$[p2,siz_y]$都在$p3$右边，$[1,p2-1]$可以有一些在$p3$右边，有一些在左边

所以$p3$的左边数的数量限制是：$p1-1\leq p3-1\leq p1-1+p2-1$，也就是$p1\leq p3\leq p1+p2-1$

$p3$的范围就确定了，转移当然还要乘组合数，先考虑左边的情况，左边有$p3-1$个点，一定有$p1-1$个来自$x$的原序列，所以左边的方案数为$C_{p3-1}^{p1-1}$；右边同理，有$siz_x+siz_y-p3$个点，一定有$siz_x-p1$个点来自$x$的原序列，所以右边方案数是$C_{siz_x+siz_y-p3}^{siz_x-p1}$。

综上，从$f[x][p1],f[y][p2]$转移到$newf[x][p3]$，而且新序列中$x$在$y$左边，要满足$p1\leq p3\leq p1+p2-1$，转移方程是

$newf[x][p3]+=C_{p3-1}^{p1-1}C_{siz_x+siz_y-p3}^{siz_x-p1}f[x][p1]f[y][p2]$

还有一种情况就是新序列中$x$在$y$右边的，也是同理推，转移方程一样，唯一的区别是$p3$的取值范围是$p1+p2\leq p3\leq p1+siz_x$。

然后就解决了，然而是$O(n^3)$的，考虑优化

当然把式子写出来啊（还是以新序列中$x$在$y$左边为例）

for p1 in [1,siz_x]
    for p2 in [1,siz_y]
        for p3 in [p1,p1+p2-1]
            转移

观察一下转移方程，好像$p2$只出现了一次，还是连续的，于是调换循环顺序（省去对循环范围的推倒）：

for p1 in [1,siz_x]
    for p3 in [p1,p1+siz_y-1]
        for p2 in [p3-p1+1,siz_y]
            转移

那么把循环转移成了p2最后一个循环，就可以用前缀和优化转移了，然后这题切了。。。

就是新序列中$x$在$y$右边的情况直接看代码。

#include<bits/stdc++.h>
#define il inline
#define vd void
#define mod 1000000007
typedef long long ll;
il ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return x*f;
}
int fir[1010],dis[2010],nxt[2010],w[2010],id;
il vd link(int a,int b,int c){nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c;}
int f[1010][1010],g[1010],siz[1010];
int C[1010][1010];
il vd dfs(int x){
	siz[x]=1;f[x][1]=1;
	for(int i=fir[x];i;i=nxt[i]){
		if(siz[dis[i]])continue;
		dfs(dis[i]);
		memcpy(g,f[x],sizeof g);
		memset(f[x],0,sizeof f[x]);
		if(w[i]==1){
			for(int p1=1;p1<=siz[x];++p1)
				for(int p3=p1;p3<p1+siz[dis[i]];++p3)
					f[x][p3]=(f[x][p3]+1ll*C[siz[x]+siz[dis[i]]-p3][siz[x]-p1]*C[p3-1][p1-1]%mod*g[p1]%mod*(f[dis[i]][siz[dis[i]]]-f[dis[i]][p3-p1]+mod))%mod;
		}else{
			for(int p1=1;p1<=siz[x];++p1)
				for(int p3=p1+1;p3<=p1+siz[dis[i]];++p3)
					f[x][p3]=(f[x][p3]+1ll*C[siz[x]+siz[dis[i]]-p3][siz[x]-p1]*C[p3-1][p1-1]%mod*g[p1]%mod*f[dis[i]][p3-p1])%mod;
		}
		siz[x]+=siz[dis[i]];
	}
	for(int i=1;i<=siz[x];++i)f[x][i]=(f[x][i]+f[x][i-1])%mod;
}
int main(){
#ifdef XZZSB
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	C[0][0]=1;
	for(int i=1;i<=1000;++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;
	}
	int T=gi();
	while(T--){
		id=0;memset(fir,0,sizeof fir);memset(siz,0,sizeof siz);
		int n=gi(),a,b;char ch;
		for(int i=1;i<n;++i){
			scanf("%d %c %d",&a,&ch,&b);++a,++b;
			link(a,b,ch=='<');link(b,a,ch=='>');
		}
		dfs(1);
		printf("%d\n",f[1][n]);
	}
	return 0;
}