[LibreOJ 3124]【CTS2019】氪金手游【容斥原理】【概率】【树形DP】

Description

Solution

首先它的限制关系是一个树形图

首先考虑如果它是一个外向树该怎么做。

这是很简单的，我们相当于每个子树的根都是子树中最早出现的点，概率是容易计算的。

设DP状态\(f[i][j]\)为做到以i为根的子树，子树中权值W的和为j且满足限制关系的概率。

然后就可以直接利用子树背包DP来转移了。

如果有些边是反向（儿子到父亲）的，我们可以通过容斥来把这些边反过来，要么是彻底没有这条边的限制，要么是反向变成父亲到儿子方向，系数乘一个(-1)即可。

具体可以参考代码。

Code

#include <bits/stdc++.h>

#define fo(i,a,b) for(int i=a;i<=b;++i)

#define fod(i,a,b) for(int i=a;i>=b;--i)

#define N 1005

#define LL long long

#define mo 998244353

using namespace std;

int n,fs[N],nt[2*N],dt[2*N],sz[N],m1;

LL ny[N],ap[N][4],f[N][3*N],pr[2*N],g[3*N],np[3*N];

LL ksm(LL k,LL n)

{

	LL s=1;

	for(;n;n>>=1,k=k*k%mo) if(n&1) s=s*k%mo;

	return s;

}

void link(int x,int y)

{

	nt[++m1]=fs[x];

	dt[fs[x]=m1]=y;

}

void dfs(int k,int fa)

{

	f[k][0]=1;

	for(int i=fs[k];i;i=nt[i])

	{

		int p=dt[i];

		if(p!=fa)

		{

			dfs(p,k);

			fo(x,0,3*sz[k])

				fo(y,1,3*sz[p])

				{

					(g[x+y]+=f[k][x]*f[p][y]%mo*pr[i]%mo)%=mo;

					if(pr[i]==mo-1) (g[x]+=f[k][x]*f[p][y]%mo)%=mo;

				}

			sz[k]+=sz[p];

			fo(j,0,3*sz[k]) f[k][j]=g[j],g[j]=0;

		}

	}

	sz[k]++;

	fod(i,3*sz[k],0)

	{

		f[k][i]=0;

		fo(j,1,3) if(i>=j) (f[k][i]+=f[k][i-j]*ny[k]%mo*ap[k][j]%mo*np[i]%mo*(LL)j%mo)%=mo;

	}

}

int main()

{

	cin>>n;

	fo(i,1,n)

	{

		fo(j,1,3) scanf("%d",&ap[i][j]),ny[i]+=ap[i][j];

		ny[i]=ksm(ny[i]%mo,mo-2);

	}

	fo(i,1,3*n) np[i]=ksm(i,mo-2);

	fo(i,1,n-1)

	{

		int x,y;

		scanf("%d%d",&x,&y);

		link(x,y),link(y,x);

		pr[m1-1]=1,pr[m1]=mo-1;

	}

	dfs(1,0);

	LL ans=0;

	fo(i,1,3*n) (ans+=f[1][i])%=mo;

	printf("%lld\n",ans);

}

巴特西

[LibreOJ 3124]【CTS2019】氪金手游【容斥原理】【概率】【树形DP】

Description

Solution

Code

最新文章

热门文章