P4099 [HEOI2013]SAO

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

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

树形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;

}

巴特西

P4099 [HEOI2013]SAO

P4099 [HEOI2013]SAO

最新文章

热门文章