正題

題目鏈接:https://ac.nowcoder.com/acm/contest/11161/C

---

題目大意

$n$個(gè)點(diǎn)加$m$條邊使得不存在環(huán)，每種方案的權(quán)值是所有聯(lián)通塊的大小乘積。

求所有方案的權(quán)值和。

$1\le n\le 10^9,1\le m\le 10^7$

---

解題思路

就是分成$n?m$個(gè)樹，然后權(quán)值比較麻煩。

但是發(fā)現(xiàn)權(quán)值是大小，所以可以理解為有根樹，這樣就是純粹的求方案數(shù)了。

然后我們還可以優(yōu)化，設(shè)虛根$0$，我們限制其度數(shù)為$n?m$就可以分為$n?m$個(gè)有根樹了。

所以用$Prufer$序列統(tǒng)計(jì)的話方案數(shù)就是
$$\left(\genfrac{}{}{0ex}{}{n?1}{m}\right)\times n^m$$

時(shí)間復(fù)雜度$O(n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll P=1e9+7; ll n,m,C,inv[11000000]; 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; } signed main() {scanf("%lld%lld",&n,&m);ll C=1;for(ll i=1;i<=m;i++)C=C*(n-i)%P;inv[1]=1;for(ll i=2;i<=m;i++)inv[i]=P-inv[P%i]*(P/i)%P,C=C*inv[i]%P;printf("%lld\n",C*power(n,m)%P); }

總結(jié)

以上是生活随笔為你收集整理的牛客挑战赛48C-铬合金之声【Prufer序列】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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