每月一题2019.6

题面:

输出n个点的形态不同的森林对998244353取模的结果。

题解:

这是经典题诶,主要考察会不会真正的分治FFT啦。

设n个点的无标号有根树有$f_n$个,对应的生成函数为$F(x)$。

对于一棵树而言,去掉根节点之后的各个部分互不关联,又因为没有标号,所以可以看作是一个背包的关系。那么枚举与根相连的子树大小,将背包的生成函数套进去:

这个式子就相当于枚举大小为$k$的子树,因为大小为$k$的子树有$f_k$种选法,每一种有都有无限多个,所以总贡献是右边那一堆东西。而这个总贡献有没有计算根的大小,那么就再在左边乘上一个$x$。

熟悉生成函数的话,就可以话建议下右边的部分:

这个时候$[x^n]$就可以拿掉了:

连乘转连加的话就是$\ln$了吧,那么就对数:

对数不好处理,求导:

两边同时乘上$xF(x)$,去掉分母:

放$[x^n]$上去:

因为有:

所以可以带入原式:

转化一下:

将右边的部分当做另一个多项式的$n-i$项,那么这就是一个类似卷积的形式,考虑用分治$FFT$优化。

基于调和级数,已知$F(x)$的话暴力计算右边的辅助多项式(设为$G(x)$)的复杂度只有$O(nlogn)$,那么就只用考虑如何计算分治时左边对右边的贡献。

因为$G(x)$的位数不够,当分治的左端点不为$1$时左区间对右边的贡献不能完全计算。所以就先不计算这部分的贡献,改为在计算出一段$G(x)$后卷积两次来完整计算左区间的贡献(一遍$F(x)$一遍$G(x)$)。

具体实现的时候为了计算贡献时的方便就将位数补到$2^k$不然非常难写。

现在已经求出了$n$个点的无标号有根树的数量,考虑使用容斥转化出为标号无根树的数量。

因为一棵树的重心非常少并且可以用子树大小来描述,那么就使用容斥去掉所有根不为重心的子树,具体来说就是枚举有哪些树的根包含一个子树的大小大于整棵树大小的一半就可以解决了。

实际实现的时候考虑枚举断掉原来树的一条中心边来处理,下面假设$h_n$为$n$的无标号无根树的数量。

因为偶数个节点的树可能有两个重心,枚举判掉即可。

那么这个东西的中间的部分很明显是一个卷积,$O(nlogn)$求出来然后$O(n)$加加减减就可以求出$\{h_n\}$。

然后现在知道了无标号的树的数量,怎么计算无标号森林的数量呢?

一颗森林由若干棵树组成,互相之间没有影响,也没有顺序,那么就相当于一个背包:大小为$k$的物品有$h_k$种。

设恰好装成体积为$n$的方案数为$g_n$,其数列对应的形式幂级数为$G(x)$:

非常眼熟对吧,那么就求$\ln$:

而又因为:

基于调和级数,这个东西是可以$O(nlogn)$暴力计算出来的,那么就可以求出$\ln{G(x)}$,再做一个$\exp$就可以求出$G(x)$了。

总复杂度$O(nlog^2n)$,但是因为分治FFT的小常数跑起来相当快。

下面是代码环节:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1<<19|1,mod=998244353,G=3,inv3=332748118,inv2=mod+1>>1;
#define re register
#define I inline int
#define V inline void
#define ll long long int
#define FOR(i,A,B) for(re int i=A;i<=B;++i)
#define ROF(i,A,B) for(re int i=A;i>=B;--i)
ll Pow(ll t,int x){
ll s=1;
for(;x;x>>=1,t=t*t%mod)
if(x&1)s=s*t%mod;
return s;
}
namespace poly{
int lmt(1),r[N],w[N],inv[N];
V init(int n){
int l=0;inv[0]=inv[1]=1;
FOR(i,2,n)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
while(lmt<=n)lmt<<=1,++l;
FOR(i,1,lmt-1)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
int wn=Pow(3,(mod-1)>>l);w[lmt>>1]=1;
FOR(i,(lmt>>1)+1,lmt-1)w[i]=(ll)w[i-1]*wn%mod;
ROF(i,(lmt>>1)-1,1)w[i]=w[i<<1];
lmt=__builtin_ctz(lmt);
}
I getLen(int n){return 1<<(32-__builtin_clz(n));}
V DFT(int*a,int l){
static unsigned long long int tmp[N];
re int u(lmt-__builtin_ctz(l)),t;
FOR(i,0,l-1)tmp[i]=a[r[i]>>u];
for(re int i=1;i<l;i<<=1)
for(re int j=0,step=i<<1;j<l;j+=step)
FOR(k,0,i-1)
t=tmp[i+j+k]*w[i+k]%mod,tmp[i+j+k]=tmp[j+k]+mod-t,tmp[j+k]+=t;
FOR(i,0,l-1)a[i]=tmp[i]%mod;
}
V IDFT(int*a,int l){
reverse(a+1,a+l),DFT(a,l);
re int bk(mod-(mod-1)/l);
FOR(i,0,l-1)a[i]=(ll)a[i]*bk%mod;
}
V get_inv(const int*a,int*b,int n){
if(n==1)return void(b[0]=Pow(a[0],mod-2));
static int tmp[N],l;
get_inv(a,b,(n+1)>>1),l=getLen(n<<1);
FOR(i,0,n-1)tmp[i]=a[i];
FOR(i,n,l-1)tmp[i]=0;
DFT(tmp,l),DFT(b,l);
FOR(i,0,l-1)b[i]=(2ll-1ll*tmp[i]*b[i]%mod+mod)%mod*b[i]%mod;
IDFT(b,l);FOR(i,n,l-1)b[i]=0;
}
V deri(const int*a,int*b,int n){FOR(i,0,n-2)b[i]=1ll*a[i+1]*(i+1)%mod;}
V inte(const int*a,int*b,int n){FOR(i,1,n-1)b[i]=1ll*a[i-1]*inv[i]%mod;}
V Ln(const int*a,int*b,int n){
static int tmp[N],l;
deri(a,b,n),get_inv(a,tmp,n),l=getLen(n<<1);
DFT(b,l),DFT(tmp,l);
FOR(i,0,l-1)tmp[i]=1ll*b[i]*tmp[i]%mod;
IDFT(tmp,l);FOR(i,0,l-1)b[i]=0;
inte(tmp,b,n);FOR(i,0,l-1)tmp[i]=0;
}
V exp(const int*a,int*b,int n){
static int tmp[N],l;
if(n==1)return void(b[0]=1);
exp(a,b,(n+1)>>1),Ln(b,tmp,n),l=getLen(n<<1);
FOR(i,0,n-1)tmp[i]=(a[i]-tmp[i]+mod)%mod;
FOR(i,n,l-1)tmp[i]=0;
++tmp[0],DFT(tmp,l),DFT(b,l);
FOR(i,0,l-1)b[i]=1ll*tmp[i]*b[i]%mod;
IDFT(b,l);FOR(i,n,l-1)b[i]=tmp[i]=tmp[i-n]=0;
}
}
using poly::inv;
using poly::DFT;
using poly::IDFT;
using poly::getLen;
int f[N],g[N],n,m,k,h[N];
V init(const int&x){
if(x^1)f[x]=1ll*f[x]*Pow(x-1,mod-2)%mod;
else f[x]=1;
for(re int j=x,t=1ll*f[x]*x%mod;j<=n;j+=x)g[j]=(g[j]+t)%mod;
}
#define mul() DFT(X,l),DFT(Y,l);FOR(i,0,l-1)X[i]=1ll*X[i]*Y[i]%mod;IDFT(X,l);
V cdq(int L,int R){
if(L==R)return init(L);
static int X[N],Y[N];
re int mid=L+R>>1,l;
cdq(L,mid);
if(L==1){
FOR(i,L,mid)X[i-L]=f[i],Y[i-L]=g[i];
l=getLen(R-L),mul();
FOR(i,mid+1,R)f[i]=(f[i]+X[i-L-1])%mod;
FOR(i,0,l-1)X[i]=Y[i]=0;
}
else{
l=getLen(R+mid-L-L+1);
FOR(i,L,mid)X[i-L]=f[i];
FOR(i,1,R-L)Y[i-1]=g[i];mul()
FOR(i,mid+1,R)f[i]=(f[i]+X[i-L-1])%mod;
FOR(i,0,l-1)X[i]=Y[i]=0;
FOR(i,L,mid)X[i-L]=g[i];
FOR(i,1,R-L)Y[i-1]=f[i];mul()
FOR(i,mid+1,R)f[i]=(f[i]+X[i-L-1])%mod;
FOR(i,0,l-1)X[i]=Y[i]=0;
}
cdq(mid+1,R);
}
int A[N],B[N],fac[N];
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
cin>>n,n++,m=n,n=getLen(n),poly::init(n),cdq(1,n),n=m;
re int l=getLen(n+n);
static int X[N];
FOR(i,0,l-1)X[i]=f[i]*(i<=n);DFT(X,l);
FOR(i,0,l-1)X[i]=1ll*X[i]*X[i]%mod;IDFT(X,l);
FOR(i,1,n)
if(i&1)h[i]=(f[i]+mod-1ll*X[i]*inv2%mod)%mod;
else
X[i]=(X[i]-1ll*f[i>>1]*f[i>>1]%mod+mod)%mod,
h[i]=((ll)f[i]+mod*2-1ll*X[i]*inv2%mod-(1ll*f[i>>1]*(f[i>>1]-1)>>1)%mod)%mod;
FOR(i,1,n)FOR(j,1,n/i)
A[j*i]=(A[j*i]+1ll*h[i]*inv[j]%mod)%mod;
poly::exp(A,B,n),n--,cout<<B[n];
return 0;
}

实际上也不是很难对吧,在校内考试的时候出了这道题结果居然全员爆0了,出来个把人输出了样例之外大部分人甚至连源代码都没交233。

(明明$O(n^2)$很好想的$da\star{ze}$)