2024.8.11 鮮花
花の塔
君が持ってきた漫畫
くれた知らない名前のお花
今日はまだ來ないかな?
初めての感情知ってしまった
窓に飾った絵畫をなぞってひとりで宇宙を旅して
それだけでいいはずだったのに
君の手を握ってしまったら
孤獨を知らないこの街には
もう二度と帰ってくることはできないのでしょう
君が手を差し伸べた 光で影が生まれる
歌って聞かせて この話の続き
連れて行って見たことない星まで
誰の手も聲も屆かない
高く聳え立った塔の上へ
飛ばすフウセンカズラ
僕は君に笑って欲しいんだ
満たされない穴は惰性の會話や澄ましたポーズで
これまでは埋めてきたけど
退屈な日々を蹴散らして
君と二人でこの街中を泳げたら
それはどれだけ素敵なことでしょう?
出したことないほど大きな聲でやっと君に伝わる
歪なくらいがさ きっとちょうどいいね
世界の端と端を結んで
窓に飾った絵畫をなぞってひとりで宇宙を旅して
それだけでも不自由ないけど
僕は選んでみたいの
高鳴る心 謎だらけの空を
安全なループを今、書き換えて!
君の手を握ってしまったら
孤獨を知らないこの街にはもう二度と
帰ってくることはできないのでしょう
いくらでも迷いながら光も影も見に行こう
歌って聞かせてこの話の続き
連れて行って見たことない星まで
世界の端と端を結んで

當然只有 \(op=1\)
有容斥做法,下次說,這里主要講 jijidawang 的好做法。
一下稱第一棵樹(已知樹)為 A,第二棵(未知樹)為 B。
首先發(fā)現(xiàn) B 的貢獻只和其是否對應 A 的邊有關,所以根據(jù)其是否是 A 的邊將 B 劃分成連通塊。
設連通塊數(shù)為 \(k\),則一種樹貢獻為 \(y^k\)
考慮將 \(k\) 個連通塊拼成樹的方案為 \(n^{k-2}\prod s_i\) 其中 \(s_i\) 為連通塊大小。
但是這樣如果用樹邊連接有拼重的,考慮新設一個貢獻 \(v\) 使答案正確。
枚舉樹邊的連接個數(shù),對于一種樹貢獻是 \(\sum\limits_{i=0}^{n-k}\dbinom{n-k}{i}v^{k+i}\)。通過二項式定理得 \(v^k(1+v)^{n-k}\)
將 \((1+v)^n\) 提出來,最后在除上,聯(lián)立 \(v^k(1+v)^{n-k}=y^k\) 解得 \(v=\frac{y}{1-y}\)
所以現(xiàn)在就是求:
簡單化簡一下就是:
前面的顯然整,后面已經(jīng)可以 \(n^2\) dp 做了。
考慮繼續(xù)推:
發(fā)現(xiàn)后面相當于在每個聯(lián)通塊里選個點做出 \(nv\) 的貢獻,最后求和,設 \(dp_{i,0/1}\) 表示 \(i\) 為根是否已經(jīng)選了點,可以省掉枚舉 \(k\),做到 \(O(n)\)。
Code
#include<bits/stdc++.h>
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
#define endl '\n'
#ifdef LOCAL
FILE *InFile=freopen("in_out/in.in","r",stdin),*OutFile=freopen("in_out/out.out","w",stdout);
#else
FILE *InFile=stdin,*OutFile=stdout;
#endif
const int N=1e5+3,MOD=998244353;
struct Gph{
int hd[N],nt[N<<1],to[N<<1],tot=1;
void Add(int u,int v){to[++tot]=v,nt[tot]=hd[u],hd[u]=tot;}
void ADD(int u,int v){Add(u,v),Add(v,u);}
#define For_to(i,u,v,g) for(int i=g.hd[u],v=g.to[i];i;i=g.nt[i],v=g.to[i])
}g;
int Fpw(int a,int b){
int ans=1;
while(b){
if(b&1) ans=1ll*ans*a%MOD;
a=1ll*a*a%MOD,b>>=1;
}
return ans;
}
int Inv(int a){return Fpw(a,MOD-2);}
int n,y,v; ull dp[N][2];
void Dp(int u,int f){
dp[u][0]=1,dp[u][1]=1ll*v*n%MOD;
For_to(i,u,v,g) if(v!=f){
Dp(v,u);
dp[u][1]=dp[v][0]*dp[u][1]%MOD+dp[v][1]*dp[u][0]%MOD+dp[v][1]*dp[u][1]%MOD;
dp[u][0]=dp[v][0]*dp[u][0]%MOD+dp[v][1]*dp[u][0]%MOD;
}
}
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>y;
if(y==1) return cout<<Fpw(n,n-2),0;
for(int i=1;i<n;++i){int u,v; cin>>u>>v; g.ADD(u,v);}
v=1ll*y*Inv(1-y+MOD)%MOD; Dp(1,0);
cout<<dp[1][1]*(Fpw(1-y,n)+MOD)%MOD*Inv(1ll*n*n%MOD)%MOD;
}
提前祝賀木子米醬贏得本屆挺王寶座(怎么上貼吧啊?。?/summary>


本文來自博客園,作者:xrlong,轉載請注明原文鏈接:http://www.rzrgm.cn/xrlong/p/18353920
版權聲明:本作品采用 「署名-非商業(yè)性使用-相同方式共享 4.0 國際」許可協(xié)議(CC BY-NC-SA 4.0) 進行許可。

浙公網(wǎng)安備 33010602011771號