目錄

• UOJ351 新年的葉子
• 題意
• 題解
• Code:

UOJ351 新年的葉子

題目傳送門

題意

躲過了\(AlphaGo\)之后，你躲在\(SingleDog\)的長毛里，和它們一起來到了\(AlphaGo\)的家。此時你們才突然發(fā)現(xiàn)，\(AlphaGo\)的家居然是一個隱藏在地下的計算中心！難道\(AlphaGo\)如此人贏的秘密是...它其實是一個\(AI\)？
根據(jù)情報，這個地下的計算中心的結構構成了一棵無根樹，整個計算中心名為被\(AT-field\)的力場保護起來，保護力場的直徑恰好等于樹的直徑（樹的直徑定義為樹上距離最遠的兩個結點之間的距離，結點 \(u\),\(v\) 的距離定義為從 \(u\) 到 \(v\) 最少需要經(jīng)過的邊數(shù)）。
由于保護力場的存在，\(SingleDog\)們每次只能進入整棵樹的一個葉子（度為1的結點），由于狗的大腦很小，他們每次只會隨機進攻一個原樹的葉子，并且破壞里面的設備，更加狼狽的是他們甚至會重復進入一個已經(jīng)被破壞過的葉子。
他們想知道，期望多少次之后，可以使得保護力場的直徑縮小？
即，對于一棵樹，每次隨機染黑一個葉子（可能會重復染黑），期望多少次后直徑變小？

輸入格式
從標準輸入讀入數(shù)據(jù)。
第一行一個正整數(shù)\(n\)，表示樹的點數(shù)。
接下來\(n?1\)行，每行兩個正整數(shù)\(x\),\(y\)，表示樹上的一條邊。
輸出格式
輸出到標準輸出。
輸出一行一個整數(shù)表示答案在模 \(998244353\) 意義下的取值。
即設答案化為最簡分式后的形式為 \(\frac{a}\) ，其中 \(a\) 和 \(b\) 互質。輸出整數(shù) \(x\) 使得 \(x \equiv a \pmod{998244353}\)且 \(0 \leq x < 998244353\)。可以證明這樣的整數(shù) \(x\) 是唯一的。

題解

首先一點可以發(fā)現(xiàn)的是，我們所需要的點只是所有直徑的兩個端點，而其余的都是沒有用的點，因為改變了其余的點，是不能夠達成第一次改變樹的直徑的條件的。然后我們分直徑的奇偶進行討論:

• 如果直徑為奇數(shù)，那么我們一定可以找到中間的那條邊，滿足所有的直徑都經(jīng)過那一條邊。那么我們會發(fā)現(xiàn)，所有的有用點會被分為兩個點集，分別是在中間那條邊的左邊與右邊。直徑會發(fā)生改變當且僅當只剩下了某一個點集。
• 如果直徑為偶數(shù)，那么我會可以找到中間的一個點，滿足所有的直徑都經(jīng)過這個點。那么我們以這個點為根，構建一棵有根樹，所有的有用點會根據(jù)其所處于根節(jié)點的哪棵子樹里被劃分成若干個點集。所以所有的直徑都是從某一個點集中的一個點出發(fā)，到達另一個點集中，直徑會發(fā)生改變當且僅當我們刪除到只剩下一個點集。

現(xiàn)在我們已經(jīng)將所有有用的葉子節(jié)點分成了若干個集合，所以我們開始計算每一個集合的貢獻（即最后只剩下這個集合）。這里，我們設這個集合的點數(shù)為\(d\)，所有集合總點數(shù)為\(d0\)，葉子節(jié)點的總點數(shù)為\(m\)。
首先我們枚舉我們所選的集合最后會剩下多少個點\(i (1 \leq i \leq d0-1)\)，那么這\(i\)個點的總選擇方案為\(\tbinom{d0}{i}\)。由于我們要求刪掉所有集合只剩下所選的集合，并且為了滿足是在刪掉最后一個點之后才是第一次改變直徑，我們最后一個刪掉的點一定不能是所選集合中的點。然后我們考慮前面刪點的方案，這個隨機刪點的方法似乎比較的不靠譜，于是我們考慮轉化一下問題。我們假設當前還有\(x\)個葉子節(jié)點沒有刪，那么刪掉一個葉子節(jié)點的代價是\(\frac{m}{x}\)，那么問題就轉化成了刪掉每一個點有一個代價，要求給定一個刪除的方案，求總代價。然后這個方案數(shù)實際上就是待刪除節(jié)點的階乘。所以我們現(xiàn)在總共要刪掉的節(jié)點數(shù)是\(d0-d+i-1\)（減一是因為有一個非所選集合的點一定要最后刪，這個點的位置已經(jīng)定下來了），總共的方案數(shù)為\((d0-d+i-1)!\)，然后最后刪除的點的選擇方案有\((d0-d)\)中，所以實際的方案數(shù)是\((d0-d+i-1)!*(d0-d)\)，刪除這些節(jié)點的總共代價是\(\sum_{j=d-i+1}^{d0}\frac{m}{j}\)。刪除這些節(jié)點之后，由于我們的操作次數(shù)是無限次，所以所有的葉子節(jié)點最后都一定會被刪除掉，那么剩余的那些沒有用的葉子節(jié)點總共的刪除方案個數(shù)為\((d-i)!\)種。最后要求的是期望，所以還要除以一個總共的方案數(shù)\(d0!\)。
所以最后對于某一個集合的答案計算的公式如下:
\(\sum_{i=1}^ze8trgl8bvbq\tbinom{d0}{i}*(d0-d+i-1)!*(d0-d)*(\sum_{j=d-i+1}^{d0}\frac{m}{j})*(d-i)!*\frac{1}{d0!}\)
里面的階乘，階乘逆元，\(\sum_j \frac{m}{j}\)可以預處理，組合數(shù)可以直接算，總共的復雜度為\(O(n)\)

Code:

#pragma GCC optimize (2,"inline","Ofast") #include<bits/stdc++.h> using namespace std; const int N=5e5+500; const int Md=998244353; typedef long long ll; int n; int fac[N],Inv[N]; inline int Add(const int &x,const int &y) {return x+y>=Md?(x+y-Md):(x+y);} inline int Sub(const int &x,const int &y) {return x-y<0?(x-y+Md):(x-y);} inline int Mul(const int &x,const int &y) {return (ll)x*y%Md;} int Powe(int x,int y) {int res=1;while(y) {if(y&1) res=Mul(res,x);x=Mul(x,x);y>>=1;}return res; }struct edge {int to,nxt; }E[N<<2]; int tot,setc,Hd,totc,totlf; int head[N],dis[N],fa[N],cnt[N],vis[N],isf[N],in[N],sum[N],inv[N]; void Addedge(int u,int v) {E[++tot].to=v;E[tot].nxt=head[u];head[u]=tot;E[++tot].to=u;E[tot].nxt=head[v];head[v]=tot; }void Dfs(int o,int ff,int d) {dis[o]=d;fa[o]=ff;for(int i=head[o];~i;i=E[i].nxt) {int to=E[i].to;if(to==ff) continue;Dfs(to,o,d+1);} }void Get(int o,int ff,int ds,int st) {if(isf[o]&&ds==Hd) cnt[st]++,totc++;vis[o]=1;for(int i=head[o];~i;i=E[i].nxt) {int to=E[i].to;if(to==ff||vis[to]) continue;Get(to,o,ds+1,st);} }void Init() {fac[0]=1;for(int i=1;i<=500000;i++) {fac[i]=(ll)fac[i-1]*i%Md;}Inv[500000]=Powe(fac[500000],Md-2);for(int i=500000-1;i;i--) {Inv[i]=(ll)Inv[i+1]*(i+1)%Md;}Inv[0]=1;sum[1]=1;inv[0]=inv[1]=1;for(int i=2;i<=n;++i) {inv[i]=Mul(inv[Md%i],(Md-Md/i));sum[i]=Add(sum[i-1],inv[i]);} }int C(int n,int m) {assert(n>=m);return (ll)fac[n]*Inv[m]%Md*Inv[n-m]%Md; }int main() {memset(head,-1,sizeof head);scanf("%d",&n);Init();for(int i=1,u,v;i<n;i++) {scanf("%d%d",&u,&v);Addedge(u,v);in[u]++;in[v]++;}for(int i=1;i<=n;i++) {if(in[i]==1) {isf[i]=1;totlf++;}}Dfs(1,1,0);int Mx=1;for(int i=1;i<=n;i++) {if(dis[i]>dis[Mx]) Mx=i;}Dfs(Mx,Mx,0);Mx=1;for(int i=1;i<=n;i++) {if(dis[i]>dis[Mx]) Mx=i;}int D=dis[Mx];Hd=dis[Mx]>>1;for(int i=1;i<=Hd;i++) Mx=fa[Mx];if(!(D&1)) {for(int i=head[Mx];~i;i=E[i].nxt) {int to=E[i].to;vis[to]=1;Get(to,Mx,1,++setc);if(!cnt[setc]) --setc;}}else {vis[Mx]=vis[fa[Mx]]=1;Get(Mx,fa[Mx],0,++setc);if(!cnt[setc]) --setc;Get(fa[Mx],Mx,0,++setc);if(!cnt[setc]) --setc;}int res=0;int d0=totc,m=totlf;for(int i=1;i<=setc;i++) {int d=cnt[i];for(int j=0;j<cnt[i];j++) {int ans=Mul(C(d,j),fac[d0-d+j-1]);ans=Mul(ans,d0-d);int S=Mul(Sub(sum[d0],sum[d-j]),m);ans=Mul(ans,S);ans=Mul(ans,fac[d-j]);ans=Mul(ans,Inv[d0]);res=Add(res,ans);}}printf("%d\n",res);return 0; }

轉載于:https://www.cnblogs.com/Apocrypha/p/9913045.html

總結

以上是生活随笔為你收集整理的UOJ351 新年的叶子的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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