生成函数

前置知识

  • 数学功底（包括但不限于基本的积分求导）

  • NTT与多项式全家桶

引入

思考

有2个红球，3个黑球，5个白球（同色球完全相同），从中任
取6个球。

  1. 有多少种不同的取法？
  2. 如果还要将取出的球排成一排，有多少种不同的排法？

问题一的答案是多项式
F(x)=(1+x+x2)(1+x+x2+x3)(1+x+x2+x3+x4+x5)F(x)=(1+x+x^2)(1+x+x^2+x^3)(1+x+x^2+x^3+x^4+x^5)
的[x6]F(x)[x^6]F(x)

从卷积形式思考很容易。

但是如何思考问题2？

我们从答案考虑如果选了a,b,ca,b,c个，那么答案为(a+b+c)!a!b!c!\frac{(a+b+c)!}{a!b!c!}，那么我们对多项式分配一下得到：

G(x)=(1+x+x22!)(1+x+x22!+x33!)(1+x+x22!+x33!+x44!)G(x)=(1+x+\frac{x^2}{2!})(1+x+\frac{x^2}{2!}+\frac{x^3}{3!})(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!})

我们的答案为6![x6]G(x)6![x^6]G(x)

可以发现，我们要求答案只与系数有关而与我们带入什么x无关，并且其中的++也是在走形式，其实际意义也不是真正的求和。

以上就是我们要探究的两类生成函数，具体的

F(x)=∑n=0∞fnxnF(x)=\sum_{n=0}^{\infty}f_nx^n 我们称之普通生成函数（ogf）

G(x)=∑n=0∞gnxnn!G(x)=\sum_{n=0}^{\infty}g_n\frac{x^n}{n!}我们称之为指数生成函数（egf）

普通生成函数

生成函数的灵魂：

∑k=0∞xk\sum_{k=0}^{\infty}x^k

等价于：

1−x∞1−x\frac{1-x^{\infty}}{1-x}

当x在(−1,1)(-1,1)间时，等价于

11−x\frac{1}{1-x}

（p.sp.s 反正xx的取值没有任何意义，怎么收敛怎么来）

整理一些基础变化问题：

  1. ∑k=0nfk{\sum_{k=0}^n}f_k

其对系数做前缀和，一个很棒的思路是转化求和，我们对其乘上∑k=0∞xk\sum_{k=0}^{\infty}x^k，此时每一个系数都对其之后的系数有了贡献。

F(x)∗11−xF(x)*{\frac{1}{1-x}}

  1. ∑n=0∞( nc)xn=(1+x)c\sum_{n=0}^{\infty}( \ ^{c}_{n})x^n=(1+x)^c

基本二项式定理可得。

  1. ∑n=0∞(n+1)xn=1(1−x)2\sum_{n=0}^{\infty}(n+1)x^n=\frac{1}{(1-x)^2}

由两个∑k=0nfk{\sum_{k=0}^n}f_k相乘得到。

  1. ∑n=0∞(c+n−1n)xn=1(1−x)c\sum_{n=0}^{\infty}\binom {c+n-1} nx^n=\frac{1}{(1-x)^c}

这东西结合刚才的前缀和手玩一下可以发现。

  1. ∑n=1∞1nxn=ln⁡11−x\sum_{n=1}^{\infty}\frac{1}{n}x^n=\ln\frac{1}{1-x}

这个式子具体证明一下，方便理解生成函数的变换

原式=

∫11−xdx=ln⁡11−x\int{\frac{1}{1-x}}dx=\ln \frac{1}{1-x}

因为ln⁡(1−x′)=ln(1−x)d(1−x)dxdd(1−x)=−1(1−x)\ln (1-x')=ln(1-x)\frac{d(1-x)}{dx}\frac{d}{d(1-x)}=-\frac{1}{(1-x)}

ln⁡(11−x′)=−ln⁡(1−x′)=11−x\ln(\frac{1}{1-x'})=-\ln (1-x')=\frac{1}{1-x}

所以5成立。

例题1 CF438E The Child and Binary Tree

首先搞出dp方程式：

设fsf_s为和为ss的二叉树数目。

有

  • f0=1f_0=1

  • fn=∑j=1n∑kfk∗fn−k−cjf_n=\sum_{j=1}^n\sum_kf_k*f_{n-k-c_j}

与我们喜闻乐见的卷积形式差了一个cic_i。

既然少了，我们把它补齐就行。（构造了卷积什么都好说）

我们定理函数gi=[i∈c1,c2...,cn]g_i=[i\in{c_1,c_2...,c_n}],我们就可以把枚举cic_i变成直接与gg相乘。

即

fn=∑j∑kgjfk∗fn−k−cjf_n=\sum_{j}\sum_kg_jf_k*f_{n-k-c_j}

写成生成函数形式：

F(x)=1+∑i=1∞(∑j∑kgj∗fk∗fi−j−k)xiF(x)=1+\sum_{i=1}^{\infty}(\sum_j\sum_kg_j*f_k*f_{i-j-k})x^i

运用卷积有

F(x)=1+G(x)∗F(x)2F(x)=1+G(x)*F(x)^2

解方程得

F(x)=1+1−4G(x)2G(x)F(x)=\frac{1+\sqrt{1-4G(x)}}{2G(x)}

当然解方程得结果可能是F(x)=1−1−4G(x)2G(x)F(x)=\frac{1-\sqrt{1-4G(x)}}{2G(x)}但是我们将x=0x=0带入可以将其排除。

但是现在有一个致命的问题，G(x)G(x)没有常数项，不能求逆。于是我们将分子有理化强行构造分母的常数项。

即：

F(x)=21+1−4G(x)F(x)=\frac{2}{1+\sqrt{1-4G(x)}}

使用多项式全家桶可以优化至O(m logm)O(m\ logm)

code

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M=3e5+1,mod=998244353,G=3;

#define clr(f,n) memset(f,0,sizeof(int)*n)
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*n)

inline int getint(){
    int summ=0,f=1;char ch;
    for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
    if(ch=='-')f=-1,ch=getchar();
    for(;isdigit(ch);ch=getchar()) summ=(summ<<3)+(summ<<1)+ch-48;
    return summ*f;
}

inline int ksm(int x,int mi){
    int ans=1;
    while(mi){
        if(mi&1) ans=ans*x%mod;
        x=x*x%mod;mi>>=1;
    }
    return ans;
}

inline void qiudao(int *f,int n){
	for(int i=0;i<n;i++) f[i]=f[i+1]*(i+1)%mod;
	f[n-1]=0;
}

int inv[M];
inline void preinv(int n){
	inv[1]=1;
	for(int i=2;i<=n;i++) inv[i]=inv[mod%i]*(mod-mod/i)%mod;
}

inline void jifen(int *f,int n){
	for(int i=n;i>0;i--) f[i]=f[i-1]*inv[i]%mod;
	f[0]=0;
}

int tr[M],f[M],g[M];

inline void ntt(int *f,int op,int n){
    for(int i=1;i<n;i++) tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
    for(int i=0;i<n;i++) if(tr[i]>i) swap(f[i],f[tr[i]]);
    for(int pp=2;pp<=n;pp<<=1){
        int len=pp>>1,mi=ksm(G,(mod-1)/pp);
        if(op==-1) mi=ksm(mi,mod-2);
        for(int i=0;i<n;i+=pp){
            int ori=1;
            for(int j=i;j<i+len;j++){
                int tt=ori*f[j+len]%mod;
                f[j+len]=(f[j]-tt+mod)%mod;
                f[j]=(f[j]+tt)%mod;
                ori=ori*mi%mod;
            }
        }
    }
    if(op==-1){
        int invn=ksm(n,mod-2);
        for(int i=0;i<n;i++) f[i]=f[i]*invn%mod;
    }
}

inline void px(int *f,int *g,int n){
    for(int i=0;i<n;i++) f[i]=f[i]*g[i]%mod;
}

int _w[M],_r[M],_g[M];
#define sav _g
void invf(int *f,int m){
    #define w _w
    #define r _r
    int n=1;for(;n<m;n<<=1);
    w[0]=ksm(f[0],mod-2);
    for(int pp=2;pp<=n;pp<<=1){
        for(int i=0;i<pp/2;i++) r[i]=w[i]*2%mod;
        cpy(sav,f,pp);
        ntt(w,1,pp<<1);px(w,w,pp<<1);
        ntt(sav,1,pp<<1);px(w,sav,pp<<1);
        ntt(w,-1,pp<<1);
        for(int i=0;i<pp;i++) w[i]=(r[i]-w[i]+mod)%mod;
        clr(w+pp,pp);
    }
    cpy(f,w,m);clr(w,n*2);clr(r,n*2);clr(sav,n*2);
    #undef w
    #undef r
}

int _w2[M],_r2[M],_g2[M];
void sqrtf(int *f,int m){
    #define b _w2
    #define a _r2
    int n=1;for(;n<m;n<<=1);
    b[0]=1;
    for(int len=2;len<=n;len<<=1){
        for(int i=0;i<(len>>1);i++) a[i]=b[i]*2%mod;
        invf(a,len);
        ntt(b,1,len<<1);px(b,b,len<<1);ntt(b,-1,len<<1);
        for(int i=0;i<len;i++) b[i]=(b[i]+f[i])%mod;
        ntt(b,1,len<<1);ntt(a,1,len<<1);px(b,a,len<<1);
        ntt(b,-1,len<<1);clr(b+len,len);clr(a,len<<1);
    }
    cpy(f,b,m);clr(b,n*2);clr(a,n*2);
    #undef w
    #undef r
}

int _w3[M],_r3[M];
inline void lnf(int *f,int m){
	#define w _w3
	#define r _r3
	int n;for(n=1;n<m;n<<=1);
	cpy(w,f,m);qiudao(w,m);
	cpy(r,f,m);invf(r,n);
	ntt(w,1,n<<1);ntt(r,1,n<<1);
	px(w,r,n<<1);
	ntt(w,-1,n<<1);
	jifen(w,n<<1);
	cpy(f,w,m);clr(w,n*2);clr(r,n*2);
	#undef w
	#undef r
} 

int _w4[M],_r4[M];
inline void expf(int *f,int m){
	#define w _w4
	#define r _r4
	int n;for(n=1;n<m;n<<=1);
	w[0]=1;
	for(int len=2;len<=n;len<<=1){
		cpy(r,w,len>>1);lnf(r,len);
		for(int i=0;i<len;i++) r[i]=(f[i]-r[i]+mod)%mod;
		r[0]=(r[0]+1)%mod;		
		ntt(w,1,len<<1);ntt(r,1,len<<1);
		px(w,r,len<<1);ntt(w,-1,len<<1);		
		clr(w+len,len);clr(r,2*len);
	}
	cpy(f,w,m);clr(w,n*2);clr(r,n*2);
	#undef w
	#undef r
}

int _w5[M];
inline void ksmf(int *f,int mi,int m){
	#define w _w5
	cpy(w,f,m);lnf(w,m);
	for(int i=0;i<m;i++) w[i]=w[i]*mi%mod;
	expf(w,m);
	cpy(f,w,m);clr(w,m);
	#undef w
}

#undef sav
char s[M];
signed main(){
    int n,m;cin>>n>>m;preinv(2e5);
    int len;for(len=1;len<=m;len<<=1);
    for(int i=0;i<n;i++) f[getint()]=-4;
    f[0]++;
    sqrtf(f,len);
    f[0]=(f[0]+1)%mod;
    invf(f,len);
    for(int i=0;i<len;i++) f[i]=f[i]*2%mod;
    for(int i=1;i<=m;i++) cout<<(f[i]+mod)%mod<<"\n";
    return 0;
}

例题2 [国家集训队]整数的lqp拆分

按照套路，我们考虑答案的生成函数，注意到乘积很麻烦，优先思考乘积。

n=a+b−>ans=fa∗fbn=a+b->ans=f_a*f_b

这不是卷积形式，只不过faf_a是系数。

所以我们构造多项式第ii项是fif_i，那么把n拆分成k个数的贡献是[xn]F(x)k[x^n]F(x)^k

因为题目没要求k，所以我们手动枚举k

有：

Ans(x)=∑kF(x)k=11−F(x)Ans(x)=\sum_kF(x)^k=\frac{1}{1-F(x)}

现在目标变为求出斐波那契数列的生成函数

有如下推导

fn=fn−1+fn−2+[n=1]f_n=f_{n-1}+f_{n-2}+[n=1]

F(x)∑n=0∞(fn−1+fn−2+[n=1])xnF(x)\sum_{n=0}^{\infty}(f_{n-1}+f_{n-2}+[n=1])x^n

F(x)=x+∑(fn−1)xn+∑(fn−2)xnF(x)=x+\sum(f_{n-1})x^n+\sum(f_{n-2})x^n

F(x)=x+xF(x)+x2F(x)F(x)=x+xF(x)+x^2F(x)

所以：

F(x)=x1−x−x2F(x)=\frac{x}{1-x-x^2}

带回AnsAns，

G(x)=1+xx2+2x−1G(x)=1+\frac{x}{x^2+2x-1}

因为nn很大，直接多项式会挂掉，因此寻找封闭形式。（也就是转回多项式形式）

简单来说我们试图通过构造形如11−kx\frac{1}{1-kx}的形式。

依靠中小学数学功底，算出：

G(x)=1+122(11−(1+2)x−11−(1−2)x)G(x)=1+\frac{1}{2\sqrt2}(\frac{1}{1-(1+\sqrt2)x}-\frac{1}{1-(1-\sqrt2)x})

于是我们目标的[xn]G(x)[x^n]G(x)也就是

(1+2)n−(1−2)n22(mod1e9+7)\frac{(1+\sqrt2)^n-(1-\sqrt2)^n}{2\sqrt2}(mod 1e9+7)

我们找出2\sqrt2的二次剩余，提前跑暴力跑出来。

然后就真是数学题了。（其实从模数是1e9+7也看得出来最后答案不是用全家桶表示）

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7,er=59713600;
char s[1000001];
int ksm(int x,int mi){
	int ans=1;
	while(mi){
		if(mi&1) ans=ans*x%mod;
		x=x*x%mod;mi>>=1;
	}
	return ans;
}
signed main(){
	scanf("%s",s+1);int len=strlen(s+1);
	int n=0;
	for(int i=1;i<=len;i++) n=(n*10+s[i]-'0')%(mod-1);
	cout<<((ksm(1+er,n)-ksm(1-er,n))%mod*ksm(2*er%mod,mod-2)%mod+mod)%mod<<endl;
	return 0;
}

例题3 CF865G Flowers and Chocolate

还没看。

指数生成函数

回顾一下定义

F(x)=∑n=0∞fnxnn!F(x)=\sum_{n=0}^{\infty}f_n\frac{x^n}{n!}我们称之为指数生成函数

探究其价值，首先从其乘法开始。

egfegf的乘法：

hnn!=∑k=0nfkk!gn−k(n−k)!\frac{h_n}{n!}=\sum_{k=0}^{n}\frac{f_k}{k!}\frac{g_{n-k}}{(n-k)!}

化简得二项卷积

hn=∑k(nk)fkgn−kh_n=\sum_k \binom{n}{k}f_kg_{n-k}

其乘法意义在于合并带标号的方案，比如在第一个例子中把选出的球排成一排，实际上是给每个球一个编号。

然后你可能会有个疑惑：这不就是除以了一个全排列数量吗，把阶乘提出来然后放进fif_i里面算不是一个样？没错，这里引入这个记号的目的仅仅在于简化运算。因为有以下泰勒级数成立：

ex=1+x+x22!+...=∑i=0∞xii!e^x=1+x+\frac{x^2}{2!}+...=\sum_{i=0}^{\infty}\frac{x^i}{i!}

常见egf

  1. ∑n(cn)=(1+x)c−>∑ncnxnn!=(1+x)c\sum_n\binom{c}{n}=(1+x)^c-> \sum_nc^{\frac{n}{}}\frac{x^n}{n!}=(1+x)^c

  2. ∑n1nxn=ln⁡11−x−>∑n(n−1)!xnn!\sum_n\frac{1}{n}x^n=\ln\frac{1}{1-x}-> \sum_n(n-1)!\frac{x^n}{n!}

  3. ∑nanxnn!=eax\sum_na^n\frac{x^n}{n!}=e^{ax}

  4. ∑n[2∣n]xnn!=ex+e−x2\sum_n[2|n]\frac{x^n}{n!}=\frac{e^x+e^{-x}}{2}

现在来一波与第一类斯特林数的互动。

第一类斯特林数

将n个物品分成k个不同的轮换，写作(nk)\binom{n}{k}(打不来中括号将就一下)

思考：

  1. fn=(n1)−>F(x)=∑(n−1)!xnn!=ln⁡11−xf_n=\binom{n}{1}->F(x)=\sum(n-1)!\frac{x^n}{n!}=\ln \frac{1}{1-x}

  2. gn=(n2)−>G(x)=F(x)22!g_n=\binom{n}{2}->G(x)=\frac{F(x)^2}{2!}

  3. hn=(nk)−>H(x)=F(x)kk!h_n=\binom{n}{k}->H(x)=\frac{F(x)^k}{k!}

  4. ∑k=0n(nk)=eF(x)\sum_{k=0}^n \binom{n}{k}=e^{F(x)}

现在重点解析最后一个式子的意义（其正确性由ex=1+x+x22!+...=∑i=0∞xii!e^x=1+x+\frac{x^2}{2!}+...=\sum_{i=0}^{\infty}\frac{x^i}{i!}可知。

我们打个比方：

将n个数圆排列的egf: ln⁡11−x\ln\frac{1}{1-x}

将n个数全排列的egf：11−x\frac{1}{1-x}，改变其意义为将n个数打散为几个圆排列的组合。

发现其关系确实是expexp。

像这样，处理涉及划分的计数问题时，可以先考虑不做划分的方案数并求其egfegf，再取expexp得到答案的生成函数。

同时，利用lnln可以实现相反的过程。

例题1 城市规划

显然每一个城市带标号。

设答案的egf为F(x)F(x)

按照上述思路，一个很直观的想法是将F(x)F(x)拆成多个连通图，其egf为G(x)=eF(x)G(x)=e^{F(x)},我们考虑求出G(x)G(x)。

显然G(x)G(x)的意义就是由n个点带标号无向图数目，为

gn=2n(n−1)2g_n=2^{\frac{n(n-1)}{2}}

我们暴力求出G(x)G(x)然后求ln⁡\ln即可算出F(x)F(x)的egf，最后不要忘记乘上n!n!。

code

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M=3e5+1,mod=1004535809,G=3;

#define clr(f,n) memset(f,0,sizeof(int)*n)
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*n)

inline int getint(){
    int summ=0,f=1;char ch;
    for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
    if(ch=='-')f=-1,ch=getchar();
    for(;isdigit(ch);ch=getchar()) summ=(summ<<3)+(summ<<1)+ch-48;
    return summ*f;
}

inline int ksm(int x,int mi){
    int ans=1;
    while(mi){
        if(mi&1) ans=ans*x%mod;
        x=x*x%mod;mi>>=1;
    }
    return ans;
}

inline void qiudao(int *f,int n){
	for(int i=0;i<n;i++) f[i]=f[i+1]*(i+1)%mod;
	f[n-1]=0;
}

int inv[M];
inline void preinv(int n){
	inv[1]=1;
	for(int i=2;i<=n;i++) inv[i]=inv[mod%i]*(mod-mod/i)%mod;
}

inline void jifen(int *f,int n){
	for(int i=n;i>0;i--) f[i]=f[i-1]*inv[i]%mod;
	f[0]=0;
}

int tr[M],f[M],g[M];

inline void ntt(int *f,int op,int n){
    for(int i=1;i<n;i++) tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
    for(int i=0;i<n;i++) if(tr[i]>i) swap(f[i],f[tr[i]]);
    for(int pp=2;pp<=n;pp<<=1){
        int len=pp>>1,mi=ksm(G,(mod-1)/pp);
        if(op==-1) mi=ksm(mi,mod-2);
        for(int i=0;i<n;i+=pp){
            int ori=1;
            for(int j=i;j<i+len;j++){
                int tt=ori*f[j+len]%mod;
                f[j+len]=(f[j]-tt+mod)%mod;
                f[j]=(f[j]+tt)%mod;
                ori=ori*mi%mod;
            }
        }
    }
    if(op==-1){
        int invn=ksm(n,mod-2);
        for(int i=0;i<n;i++) f[i]=f[i]*invn%mod;
    }
}

inline void px(int *f,int *g,int n){
    for(int i=0;i<n;i++) f[i]=f[i]*g[i]%mod;
}

int _w[M],_r[M],_g[M];
#define sav _g
void invf(int *f,int m){
    #define w _w
    #define r _r
    int n=1;for(;n<m;n<<=1);
    w[0]=ksm(f[0],mod-2);
    for(int pp=2;pp<=n;pp<<=1){
        for(int i=0;i<pp/2;i++) r[i]=w[i]*2%mod;
        cpy(sav,f,pp);
        ntt(w,1,pp<<1);px(w,w,pp<<1);
        ntt(sav,1,pp<<1);px(w,sav,pp<<1);
        ntt(w,-1,pp<<1);
        for(int i=0;i<pp;i++) w[i]=(r[i]-w[i]+mod)%mod;
        clr(w+pp,pp);
    }
    cpy(f,w,m);clr(w,n*2);clr(r,n*2);clr(sav,n*2);
    #undef w
    #undef r
}

int _w2[M],_r2[M],_g2[M];
void sqrtf(int *f,int m){
    #define b _w2
    #define a _r2
    int n=1;for(;n<m;n<<=1);
    b[0]=1;
    for(int len=2;len<=n;len<<=1){
        for(int i=0;i<(len>>1);i++) a[i]=b[i]*2%mod;
        invf(a,len);
        ntt(b,1,len<<1);px(b,b,len<<1);ntt(b,-1,len<<1);
        for(int i=0;i<len;i++) b[i]=(b[i]+f[i])%mod;
        ntt(b,1,len<<1);ntt(a,1,len<<1);px(b,a,len<<1);
        ntt(b,-1,len<<1);clr(b+len,len);clr(a,len<<1);
    }
    cpy(f,b,m);clr(b,n*2);clr(a,n*2);
    #undef w
    #undef r
}

int _w3[M],_r3[M];
inline void lnf(int *f,int m){
	#define w _w3
	#define r _r3
	int n;for(n=1;n<m;n<<=1);
	cpy(w,f,m);qiudao(w,m);
	cpy(r,f,m);invf(r,n);
	ntt(w,1,n<<1);ntt(r,1,n<<1);
	px(w,r,n<<1);
	ntt(w,-1,n<<1);
	jifen(w,n<<1);
	cpy(f,w,m);clr(w,n*2);clr(r,n*2);
	#undef w
	#undef r
} 

int _w4[M],_r4[M];
inline void expf(int *f,int m){
	#define w _w4
	#define r _r4
	int n;for(n=1;n<m;n<<=1);
	w[0]=1;
	for(int len=2;len<=n;len<<=1){
		cpy(r,w,len>>1);lnf(r,len);
		for(int i=0;i<len;i++) r[i]=(f[i]-r[i]+mod)%mod;
		r[0]=(r[0]+1)%mod;		
		ntt(w,1,len<<1);ntt(r,1,len<<1);
		px(w,r,len<<1);ntt(w,-1,len<<1);		
		clr(w+len,len);clr(r,2*len);
	}
	cpy(f,w,m);clr(w,n*2);clr(r,n*2);
	#undef w
	#undef r
}

int _w5[M];
inline void ksmf(int *f,int mi,int m){
	#define w _w5
	cpy(w,f,m);lnf(w,m);
	for(int i=0;i<m;i++) w[i]=w[i]*mi%mod;
	expf(w,m);
	cpy(f,w,m);clr(w,m);
	#undef w
}

#undef sav
char s[M];
int jie[M],nn;
signed main(){
    int n;cin>>n;preinv(n<<1);
    jie[0]=1;
    for(int i=1;i<=n;i++) jie[i]=jie[i-1]*i%mod;
	for(int i=0;i<=n;i++) f[i]=ksm(2,i*(i-1)/2)*ksm(jie[i],mod-2)%mod;
	lnf(f,n+1);
    cout<<(jie[n]*f[n]%mod+mod)%mod<<endl;
    return 0;
}

（一点补充：此题是由连通图到无向图，如果是树的话，同理exp后表示森林）

例题2 CF623E Transforming Sequence

第一步脑补出dp方程。

我们设f[a][b]f[a][b]为a个位置可选用b个元素的方案数（b必须全用）。

有：

f[a][b]=∑k=0b−1(bk)2kf[a−1][k]f[a][b]=\sum_{k=0}^{b-1}\binom{b}{k}2^kf[a-1][k]

（真的想了很久）

解释一下就是添加最后一项，其中枚举之前用了几个元素，那么最后添加的一项这些元素随便选或不选，剩下的必须选。

注意到dp转移式的形式和我们喜闻乐见的二项卷积hn=∑k(nk)fkgn−kh_n=\sum_k \binom{n}{k}f_kg_{n-k}比较相似，我们尝试构造。

∑k=0b(bk)2kfa−1,k∗[k!=b]\sum_{k=0}^{b}\binom{b}{k}2^kf_{a-1,k}*[k!=b]

设G(x)−>ga,b=2bfa,b,G(x)=F(2x)G(x)->g_{a,b}=2^bf_{a,b}, G(x)=F(2x)

hb−k=[k!=b]h_{b-k}=[k!=b]，则ha=[a!=0]h_a=[a!=0]，H(x)=ex−1H(x)=e^x-1

现在有：

f[a][b]=∑k=0b(bk)2kfa−1,k∗[k!=b]f[a][b]=\sum_{k=0}^{b}\binom{b}{k}2^kf_{a-1,k}*[k!=b]

=∑k=0b(bk)gkhb−k=\sum_{k=0}^{b}\binom{b}{k}g_kh_{b-k}

至此我们把dp方程变成了标准的二项卷积形式，而二项卷积就是egfegf的乘法，所以：

Fa(x)=Ga−1(x)H(x)F_a(x)=G_{a-1}(x)H(x)

=Fa−1(2x)∗(ex−1)=F_{a-1}(2x)*(e^x-1)

现在又要用到数学上迭代思想，我们试图把F(x)F(x)表示为封闭形式。

Fn(x)=Fn−1(2x)(ex−1)F_n(x)=F_{n-1}(2x)(e^x-1)

Fn−1(2x)=Fn−2(4x)(e2x−1)F_{n-1}(2x)=F_{n-2}(4x)(e^{2x}-1)

......

F1(2n−1x)=F0(2nx)(e2n−1x−1)F_1(2^{n-1}x)=F_{0}(2^nx)(e^{2^{n-1}x}-1)

累乘有：

Fn(x)=F0(2nx)∏k=0n−1(e2kx−1)F_n(x)=F_0(2^nx)\prod_{k=0}^{n-1}(e^{2^kx}-1)

显然有F0(x)=1F_0(x)=1（空数列）,

所以

Fn(x)=∏k=0n−1(e2kx−1)F_n(x)=\prod_{k=0}^{n-1}(e^{2^kx}-1)

注意到连乘不好直接搞，我们试图转化为分治形式。

发现：

F2n=Fn(x)Fn(2nx)F_{2n}=F_n(x)F_n(2^nx)

(把ee的幂分成前后两段变换)

现在我们可以求F2nF_{2n}，可以求Fn+1F_{n+1},多项式倍增即可

复杂度O(k∗log⁡k∗log⁡n)O(k*\log k * \log n)

如果模数是998244353我就写了。（此题需要拆系数fft（MTT））