前言

話說在$Loj$下了個數(shù)據(jù)發(fā)現(xiàn)這題的名字叫$fgo$

---

正題

題目鏈接:https://www.luogu.com.cn/problem/P5405

---

題目大意

$n$張卡的權(quán)值為$1/2/3$的概率權(quán)重分別是$p_{x,1/2/3}$，然后按照權(quán)值每次獲得一張未獲得的卡，然后再該出一棵有向樹（方向可以都是外向或內(nèi)向的），求所有每條邊$(u,v)$，$u$都比$v$先獲得的概率。

$1\le n\le 1000,0\le p_{i,j}\le 10^6$

---

解題思路

只考慮外向樹的話就是水題了，因為顯然的$x$要排在子樹最前面的概率就是$\frac{w_x}{{\sum }_{y\in subtre{e}_x}{w}_y}$。

然后直接$n^2$的$dp$就可以力。

但是現(xiàn)在有內(nèi)向邊怎么辦，還是考慮轉(zhuǎn)換成只有外向的，也就是去掉一種限制。

去掉一種限制的話容斥是一個不錯的辦法，考慮的話就是恰好若干條指定邊（內(nèi)向邊），我們可以指定至少$k$跳內(nèi)向邊不滿足條件，這樣就組成了一個外向森林，可以很容易處理出答案，而且這樣的容斥系數(shù)就是$(?1{)}^k$。

然后直接$dp$就得了，設(shè)$f_{i,j}$表示到節(jié)點$i$然后權(quán)值和是$j$，如果限制一條內(nèi)向邊就直接乘上一個$?1$就好了。

額這種樹形$dp$枚舉子樹大小可以做到$n^2$這個是老生常談了

時間復(fù)雜度$O(n^2)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1100,P=998244353; struct node{ll to,next,w; }a[N<<1]; ll n,tot,ans,ls[N],siz[N],w[N][3],f[N][3*N],g[N*3]; ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%P;x=x*x%P;b>>=1; }return ans; } void addl(ll x,ll y,ll w){a[++tot].to=y;a[tot].next=ls[x];a[tot].w=w;ls[x]=tot;return; } void dp(ll x,ll fa){ll d=power(w[x][0]+w[x][1]+w[x][2],P-2);siz[x]=3;f[x][1]=w[x][0]*d%P;f[x][2]=w[x][1]*d*2ll%P;f[x][3]=w[x][2]*d*3ll%P;for(ll e=ls[x];e;e=a[e].next){ll y=a[e].to;if(y==fa)continue;dp(y,x);if(a[e].w){for(ll i=1;i<=siz[x];i++)for(ll j=1;j<=siz[y];j++)(g[i+j]-=f[x][i]*f[y][j]%P)%=P,(g[i]+=f[x][i]*f[y][j]%P)%=P;}else{for(ll i=1;i<=siz[x];i++)for(ll j=1;j<=siz[y];j++)(g[i+j]+=f[x][i]*f[y][j]%P)%=P;}siz[x]+=siz[y];for(ll i=1;i<=siz[x];i++)f[x][i]=g[i],g[i]=0;}for(int i=1;i<=siz[x];i++)f[x][i]=f[x][i]*power(i,P-2)%P;return; } signed main() {scanf("%lld",&n);for(ll i=1;i<=n;i++)scanf("%lld%lld%lld",&w[i][0],&w[i][1],&w[i][2]);for(ll i=1;i<n;i++){ll x,y;scanf("%lld%lld",&x,&y);addl(x,y,0);addl(y,x,1);}dp(1,0);for(ll i=1;i<=siz[1];i++)(ans+=f[1][i])%=P;printf("%lld\n",(ans+P)%P);return 0; }

總結(jié)

以上是生活随笔為你收集整理的P5405-[CTS2019]氪金手游【树形dp,容斥,数学期望】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。