【JZOJ5233】【GDOI模拟8.5】概率博弈 树形dp+期望

题面

小A和小B在玩游戏。这个游戏是这样的：
有一棵n个点的以1为根的有根树，叶子有权值。假设有m个叶子，那么树上每个叶子的权值序列就是一个1->m 的排列。
一开始在1号点有一颗棋子。两人轮流将这颗棋子移向其当前位置的一个儿子。假如棋子到达叶子，游戏结束，最终获得的权值为所在叶子对应权值。
小A希望最后的权值尽量大，小B希望尽量小。小A是先手。
在玩了很多局游戏后，小B对其中绝大多数局游戏的结果不满意，他觉得是小A对叶子权值做了手脚。于是他一怒之下，决定将叶子的权值随机排列。现在小B想知道，假如叶子的权值是随机排列的（即叶子权值的每种排列都以等概率出现），那么游戏期望的结果是多少？
请输出答案乘上m! 对10^9+7取模的结果，显然这是一个整数。
对于100%的数据，n<=5000,保证给出的是一棵合法的树。

100

首先预处理一个dp，\(f[i][j][0/1]\)表示以第i个结点为子树，填了j个0到叶子结点中，并且结点i的值为0/1，的方案数。
这个可以用树形背包弄出来，注意奇偶性。
然后就能统计答案了。
\[ Ans=\sum_{i=1}^n f[1][i][1]*i!*(sum-i)! \]

Code

#include
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;i++)
#define fd(i,x,y) for(int i=x;i>=y;i--)
using namespace std;
const char* fin="game.in";
const char* fout="game.out";
const int inf=0x7fffffff;
int read(){int x=0;char ch=getchar();while (ch<'0' || ch>'9') ch=getchar();while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x;
}
const int maxn=5007,maxm=maxn*2,mo=1000000007;
int n,fi[maxn],la[maxm],ne[maxm],tot,ans,fact[maxn];
int w[maxn],f[maxn][maxn][2],g[maxn][maxn][2];
void add_line(int a,int b){tot++;ne[tot]=fi[a];la[tot]=b;fi[a]=tot;
}
int getw(int v,int from){w[v]=0;for(int k=fi[v];k;k=ne[k])if (la[k]!=from)w[v]+=getw(la[k],v);return (w[v]?w[v]:w[v]=1);
}
void dfs(int v,int from,int x){bool az=true;for(int k=fi[v];k;k=ne[k])if (la[k]!=from){dfs(la[k],v,x^1);if (az) memcpy(f[v],f[la[k]],sizeof f[v]),az=false;else{fo(i,0,w[v]) g[v][i][0]=0,g[v][i][1]=0;fo(j,0,w[la[k]])fd(i,w[v],0){if (i+j>w[v]) continue;if (x==0){g[v][i+j][0]=(g[v][i+j][0]+1ll*f[v][i][0]*f[la[k]][j][1])%mo;g[v][i+j][0]=(g[v][i+j][0]+1ll*f[v][i][1]*f[la[k]][j][0])%mo;g[v][i+j][0]=(g[v][i+j][0]+1ll*f[v][i][0]*f[la[k]][j][0])%mo;g[v][i+j][1]=(g[v][i+j][1]+1ll*f[v][i][1]*f[la[k]][j][1])%mo;}else{g[v][i+j][1]=(g[v][i+j][1]+1ll*f[v][i][0]*f[la[k]][j][1])%mo;g[v][i+j][1]=(g[v][i+j][1]+1ll*f[v][i][1]*f[la[k]][j][0])%mo;g[v][i+j][1]=(g[v][i+j][1]+1ll*f[v][i][1]*f[la[k]][j][1])%mo;g[v][i+j][0]=(g[v][i+j][0]+1ll*f[v][i][0]*f[la[k]][j][0])%mo;}}fo(i,0,w[v]) f[v][i][0]=g[v][i][0],f[v][i][1]=g[v][i][1];}}if (az){f[v][0][1]=1;f[v][1][0]=1;}
}
int main(){freopen(fin,"r",stdin);freopen(fout,"w",stdout);scanf("%d",&n);if (n==1){printf("1");return 0;}fo(i,1,n-1){int j,k;scanf("%d%d",&j,&k);add_line(j,k);add_line(k,j);}fact[0]=1;fo(i,1,n) fact[i]=1ll*fact[i-1]*i%mo;getw(1,0);dfs(1,0,1);fo(i,0,w[1]) ans=(ans+1ll*f[1][i][1]*fact[i]%mo*fact[w[1]-i]%mo)%mo;ans=(ans+mo)%mo;printf("%d",ans);return 0;
}

转载于:https://www.cnblogs.com/hiweibolu/p/7294337.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！