該思博的時候就思博到底，套路的時候不能再套路的一道題

首先我們將聯通塊的大小平方和進行轉化，發現它就等價于連通點對數，而這個可以轉化為連接兩點的邊數（距離）和

所以我們考慮第\(i\)天時，一個點對\((x,y)\)能產生貢獻，當且僅當連接它們的邊一條都沒斷，故貢獻為：

\[\frac{(n-1-\operatorname{dis}(x,y))^{\underline i}}{(n-1)^{\underline i}}\]

因此我們發現這個東西對于所有距離相同的點對是一樣的，因此我們可以直接統計出所有的距離為\(i(i\in[0,n-1])\)的點對數\(num_i\)

然后考慮對于一天\(i\)枚舉距離為\(d\)的點對，則：

\[ans_i=\sum_{d=0}^{n-1}\frac{(n-d-1)!\times(n-i-1)!\times num_d}{(n-d-i-1)!\times(n-1)!}\]

顯然是一個卷積的形式，我們令\(A(x)=(n-i-1)!\times num_i,B(x)=\frac{1}{i!}\)，卷積之后乘回不變項然后反轉即可

那么剩下還有兩個問題，距離為\(i\)的點對數怎么求？

首先一眼點分治，然后有一個很naive的想法就是遍歷每顆子樹信息后暴力FFT合并

但這樣遇到菊花圖就直接GG了，因此我們可以容斥一下

每次以分治中心為根找出所有長度的路徑條數，然后卷積平方后減去重復在同一子樹內的部分即可，計算方法和之前一致

最后一個問題，模數不是NTT模數毒瘤出題人，難不成我們寫三模NTT？

然而發現之前FFT已經寫好了，因此我們直接拆系數做就好了

PS：本人太弱不會MTT，因此寫了最暴力的4次DFT，4次IDFT的大常數版本，復雜度就當作兩只\(\log\)來看吧

最后跑了1.36s，注意開long long和long double

CODE

#include<cstdio> #include<cctype> #include<iostream> #include<cmath> #define int LL #define RI register int #define CI const int& #define Tp template <typename T> #define CC const Complex& using namespace std; typedef long long LL; const int N=200005,INF=1e9,mod=1e9+7; const long double pi=acos(-1); class FileInputOutput {private:static const int S=1<<21;#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)#define pc(ch) (Ftop!=Fend?*Ftop++=ch:(fwrite(Fout,1,S,stdout),*(Ftop=Fout)++=ch))char Fin[S],Fout[S],*A,*B,*Ftop,*Fend; int pt[15];public:inline FileInputOutput() { Ftop=Fout; Fend=Fout+S; }Tp inline void read(T& x){x=0; char ch; while (!isdigit(ch=tc()));while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));}Tp inline void write(T x){RI ptop=0; while (pt[++ptop]=x%10,x/=10);while (ptop) pc(pt[ptop--]+48); pc(' ');}inline void flush(void){fwrite(Fout,1,Ftop-Fout,stdout);}#undef tc#undef pc }F; struct Complex {long double x,y;inline Complex(const long double& X=0,const long double& Y=0){x=X; y=Y;}friend inline Complex operator + (CC A,CC B){return Complex(A.x+B.x,A.y+B.y);}friend inline Complex operator - (CC A,CC B){return Complex(A.x-B.x,A.y-B.y);}friend inline Complex operator * (CC A,CC B){return Complex(A.x*B.x-A.y*B.y,A.x*B.y+A.y*B.x);}inline void operator /= (const long double& p){x/=p; y/=p;} }A[N<<2]; int a[N<<2],ans[N<<2],fact[N],inv[N]; struct edge {int to,nxt; }e[N<<1]; int n,head[N],cnt,x,y,dis[N],lim; class FFT_Solver {private:static const int S=ceil(sqrt(mod)),SS=1LL*S*S%mod;int rev[N<<2],p;public:inline void init(CI n){for (lim=1,p=0;lim<=n;lim<<=1,++p);for (RI i=0;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<p-1);}inline void FFT(Complex *f,CI opt){RI i; for (i=0;i<lim;++i) if (i<rev[i]) swap(f[i],f[rev[i]]);for (i=1;i<lim;i<<=1){Complex D(cos(pi/i),sin(pi/i)*opt);for (RI j=0;j<lim;j+=(i<<1)){Complex W(1,0); for (RI k=0;k<i;++k,W=W*D){Complex x=f[j+k],y=f[i+j+k]*W;f[j+k]=x+y; f[i+j+k]=x-y;}}}if (!~opt) for (i=0;i<lim;++i) f[i]/=lim;}inline void MTT(int *TA,int *TB,int *TC,CI n){static Complex A[N<<2],B[N<<2],C[N<<2],D[N<<2],E[N<<2],F[N<<2],G[N<<2],H[N<<2];RI i; for (init(n<<1),i=0;i<n;++i)A[i]=Complex(TA[i]/S),B[i]=Complex(TA[i]%S),C[i]=Complex(TB[i]/S),D[i]=Complex(TB[i]%S);for (FFT(A,1),FFT(B,1),FFT(C,1),FFT(D,1),i=0;i<lim;++i)E[i]=A[i]*C[i],F[i]=B[i]*C[i],G[i]=A[i]*D[i],H[i]=B[i]*D[i];for (FFT(E,-1),FFT(F,-1),FFT(G,-1),FFT(H,-1),i=0;i<lim;++i)TC[i]=(((LL)(E[i].x+0.5)%mod)*SS)%mod,(TC[i]+=(((LL)(F[i].x+0.5)%mod)*S)%mod)%=mod,(TC[i]+=(((LL)(G[i].x+0.5)%mod)*S)%mod)%=mod,(TC[i]+=(LL)(H[i].x+0.5)%mod)%=mod;} }P; #define to e[i].to class Point_Divide_Solver {private:int size[N],mx[N],num[N],rt,ats,mdp; bool vis[N];inline void maxer(int& x,CI y){if (y>x) x=y;}inline void getrt(CI now=1,CI fa=0){size[now]=1; mx[now]=0; for (RI i=head[now];i;i=e[i].nxt)if (to!=fa&&!vis[to]) getrt(to,now),size[now]+=size[to],maxer(mx[now],size[to]);if (maxer(mx[now],ats-size[now]),mx[now]<mx[rt]) rt=now;}inline void travel(CI now,CI fa=0,CI dep=0){maxer(mdp,dep); ++num[dep]; for (RI i=head[now];i;i=e[i].nxt)if (to!=fa&&!vis[to]) travel(to,now,dep+1);}inline void calc(CI opt){RI i; for (P.init(mdp<<1),i=0;i<=mdp;++i) A[i]=Complex(num[i],0);for (i=mdp+1;i<lim;++i) A[i]=Complex();for (P.FFT(A,1),i=0;i<lim;++i) A[i]=A[i]*A[i];for (P.FFT(A,-1),lim=min(n-1,mdp<<1),i=0;i<=lim;++i)dis[i]+=(LL)(A[i].x+0.5)%mod*opt,(dis[i]+=mod)%=mod;}inline void clear(void){for (RI i=0;i<=mdp;++i) num[i]=0;}inline void solve(CI now){RI i; mdp=0; travel(now); calc(1); clear(); vis[now]=1;for (i=head[now];i;i=e[i].nxt) if (!vis[to])mdp=0,travel(to,now,1),calc(-1),clear();for (i=head[now];i;i=e[i].nxt) if (!vis[to])mx[rt=0]=INF,ats=size[to],getrt(to,now),solve(rt);}public:inline void divide(void){mx[rt=0]=INF; ats=n; getrt(); solve(rt);} }PD; #undef to inline void addedge(CI x,CI y) {e[++cnt]=(edge){y,head[x]}; head[x]=cnt;e[++cnt]=(edge){x,head[y]}; head[y]=cnt; } inline int quick_pow(int x,int p=mod-2,int mul=1) {for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul; } inline void init(void) {RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;for (inv[n]=quick_pow(fact[n]),i=n-1;~i;--i) inv[i]=1LL*inv[i+1]*(i+1)%mod;for (i=0;i<n;++i) a[i]=1LL*fact[n-i-1]*dis[i]%mod;//for (i=0;i<n;++i) printf("%d ",a[i]); putchar('\n');//for (i=0;i<n;++i) printf("%d ",inv[i]); putchar('\n'); } signed main() {//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);RI i; for (F.read(n),i=1;i<n;++i) F.read(x),F.read(y),addedge(x,y);for (PD.divide(),init(),P.MTT(a,inv,ans,n),i=0;i<n;++i)ans[n-i-1]=1LL*ans[n-i-1]*inv[n-1]%mod*fact[n-i-1]%mod;for (i=0;i<n;++i) F.write(ans[n-i-1]); return F.flush(),0; }

轉載于:https://www.cnblogs.com/cjjsb/p/11285742.html

總結

以上是生活随笔為你收集整理的Codechef Chef Cuts Tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。