Codechef Chef Cuts Tree
2024-08-27 09:23:48
该思博的时候就思博到底，套路的时候不能再套路的一道题
首先我们将联通块的大小平方和进行转化，发现它就等价于连通点对数，而这个可以转化为连接两点的边数（距离）和
所以我们考虑第\(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;
}
最新文章
- The current identity (NT AUTHORITY/NETWORK SERVICE)
- 工欲善其事必先利其器——web调试工具firebug
- 讲讲HashCode的作用
- General Questions:Front-end Developer Interview Questions
- Oracle10g数据类型
- slidingmenu+fragment实现经常使用的側滑效果（包含Fragment状态的保存）
- Properties配置文件
- lua 类实现
- apache的keepalive和keepalivetimeout
- C++中 指针 与 引用 的区别
- jQuery中常用的函数方法
- [Linux] PHP程序员玩转Linux系列-Nginx中的HTTPS
- mybaits错误解决：There is no getter for property named 'parentId ' in class 'java.lang.String'
- 关于linux下的文件权限
- 数组的遍历你都会用了，那Promise版本的呢
- spring batch (二) 元数据表
- JAVA值传递之基本数据类型和引用数据类型
- git hub 第一篇
- vw, vh视区覆盖和自适应图片
- 20165304 2017-2018-2 《Java程序设计》第3周学习总结