生成函数

这可能是最让我摸不着头脑的知识点了......

《组合数学》第7章有很多好玩的例子。

反正说着也不清楚，还是刷题好了.....

CF438E 小朋友和二叉树。参考资料。

定义一个二叉树的权值为所有点权之和，每个点的点权只能在一个集合c中选择。问权值为1~m的树共有多少种。

设G(x)为数组c的生成函数，F(x)为我们的答案的生成函数，那么考虑它自己的关系，我们有：

F(x) = G(x)F²(x) + 1

这个毒瘤是怎么来的...G(x)是根的点权，F²(x)是两个儿子。 + 1是它作为子树可能为空树，此时有一个方案，就是常数项为1。

虽然这样说但还是不太明白.....

把上面那个方程解了，用求根公式可以得到一个东西，但是是不能直接算的，因为G(x)是分母，而常数项为0不能求逆。

于是分子有理化即可。需要多项式开根 + 多项式求逆.....

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <cmath>
  5 
  6 typedef long long LL;
  7 const int N = 100010;
  8 const LL MO = 998244353, G = 3;
  9 typedef LL arr[N << 4];
 10 
 11 arr f, g, g2, A, B, inv_t, sqrt_t, r;
 12 LL inv2;
 13 
 14 inline LL qpow(LL a, LL b) {
 15     LL ans = 1;
 16     while(b) {
 17         if(b & 1) ans = ans * a % MO;
 18         a = a * a % MO;
 19         b = b >> 1;
 20     }
 21     return ans;
 22 }
 23 
 24 inline void prework(int n) {
 25     static int R = 0;
 26     if(R == n) return;
 27     R = n;
 28     int lm = 1;
 29     while((1 << lm) < n) lm++;
 30     for(int i = 0; i < n; i++) {
 31         r[i] = (r[i >> 1] >> 1) | ((i & 1) << (lm - 1));
 32     }
 33     return;
 34 }
 35 
 36 inline void NTT(LL *a, int n, int f) {
 37     prework(n);
 38     for(int i = 0; i < n; i++) {
 39         if(i < r[i]) std::swap(a[i], a[r[i]]);
 40     }
 41     for(int len = 1; len < n; len <<= 1) {
 42         LL Wn = qpow(G, (MO - 1) / (len << 1));
 43         if(f == -1) Wn = qpow(Wn, MO - 2);
 44         for(int i = 0; i < n; i += (len << 1)) {
 45             LL w = 1;
 46             for(int j = 0; j < len; j++) {
 47                 LL t = a[i + len + j] * w % MO;
 48                 a[i + len + j] = (a[i + j] - t) % MO;
 49                 a[i + j] = (a[i + j] + t) % MO;
 50                 w = w * Wn % MO;
 51             }
 52         }
 53     }
 54     if(f == -1) {
 55         LL inv = qpow(n, MO - 2);
 56         for(int i = 0; i < n; i++) {
 57             a[i] = a[i] * inv % MO;
 58         }
 59     }
 60     return;
 61 }
 62 
 63 /*inline void mul(const LL *a, const LL *b, LL *c, int n) {
 64     int len = 1;
 65     while(len < n) len <<= 1;
 66     memcpy(A, a, n * sizeof(LL)); memset(A + n, 0, (len - n) * sizeof(LL));
 67     memcpy(B, b, n * sizeof(LL)); memset(B + n, 0, (len - n) * sizeof(LL));
 68     NTT(A, len, 1); NTT(B, len, 1);
 69     for(int i = 0; i < len; i++) c[i] = A[i] * B[i] % MO;
 70     NTT(c, len, -1);
 71     memset(c + n, 0, (len - n) * sizeof(LL));
 72     return;
 73 }*/
 74 
 75 void Inv(const LL *a, LL *b, int n) {
 76     if(n == 1) {
 77         b[0] = qpow(a[0], MO - 2);
 78         b[1] = 0;
 79         return;
 80     }
 81     Inv(a, b, n >> 1);
 82     /// ans = b * (2 - a * b)
 83     memcpy(A, a, n * sizeof(LL)); memset(A + n, 0, n * sizeof(LL));
 84     memcpy(B, b, n * sizeof(LL)); memset(B + n, 0, n * sizeof(LL));
 85     NTT(A, n << 1, 1); NTT(B, n << 1, 1);
 86     for(int i = 0; i < (n << 1); i++) b[i] = B[i] * (2 - A[i] * B[i] % MO) % MO;
 87     NTT(b, n << 1, -1);
 88     memset(b + n, 0, n * sizeof(LL));
 89     return;
 90 }
 91 
 92 inline void getInv(const LL *a, LL *b, int n) {
 93     int len = 1;
 94     while(len < n) len <<= 1;
 95     memcpy(inv_t, a, n * sizeof(LL)); memset(inv_t + n, 0, (len - n) * sizeof(LL));
 96     Inv(inv_t, b, len);
 97     memset(b + n, 0, (len - n) * sizeof(LL));
 98     return;
 99 }
100 
101 void Sqrt(const LL *a, LL *b, int n) {
102     if(n == 1) {
103         b[0] = sqrt(a[0]);
104         b[1] = 0;
105         return;
106     }
107     Sqrt(a, b, n >> 1);
108     /// ans = (b + a / b) / 2
109     Inv(b, B, n);
110     memcpy(A, a, n * sizeof(LL)); memset(A + n, 0, n * sizeof(LL));
111     NTT(A, n << 1, 1); NTT(B, n << 1, 1);
112     for(int i = 0; i < (n << 1); i++) B[i] = A[i] * B[i] % MO;
113     NTT(B, n << 1, -1);
114     for(int i = 0; i < n; i++) b[i] = (b[i] + B[i]) * inv2 % MO;
115     memset(b + n, 0, n * sizeof(LL));
116     return;
117 }
118 
119 inline void getSqrt(const LL *a, LL *b, int n) {
120     int len = 1;
121     while(len < n) len <<= 1;
122     memcpy(sqrt_t, a, n * sizeof(LL)); memset(sqrt_t + n, 0, (len - n) * sizeof(LL));
123     Sqrt(sqrt_t, b, len);
124     memset(b + n, 0, (len - n) * sizeof(LL));
125     return;
126 }
127 
128 /*inline void check() {
129     int n;
130     scanf("%d", &n);
131     for(int i = 0; i < n; i++) scanf("%lld", &f[i]);
132     getSqrt(f, g, n);
133     for(int i = 0; i < n; i++) {
134         printf("%lld ", (g[i] + MO) % MO);
135     }
136     return;
137 }*/
138 
139 int main() {
140     inv2 = (MO + 1) / 2;
141 
142     int n, m;
143     scanf("%d%d", &n, &m);
144     m++;
145     for(int i = 1, x; i <= n; i++) {
146         scanf("%d", &x);
147         g[x] = -4;
148     }
149     g[0] = 1; /// 1 - 4G
150     getSqrt(g, g2, m);
151     g2[0]++;
152     getInv(g2, g, m);
153 
154     for(int i = 1; i < m; i++) {
155         printf("%lld
", (2 * g[i] % MO + MO) % MO);
156     }
157     return 0;
158 }

AC代码

关于指数生成函数(EGF)：若f_i为得出一个大小为i的有标号集合的方案数，相应的EGF为F(x)

g_i为得出一个由若干个集合组成的大小为i的有标号大集合的方案数，G(x)为其相应的EGF。

那么有e^F(x) = G(x)，ln(G(x)) = F(x)。

你要问我为什么？背诵吧，不为什么。两个简单的例子是森林和树，图和连通图。

而且这个东西在带权的时候同样适用。具体的说，如果f_i是选出一个大小为i的集合的所有方案权值之和

g_i为所有大集合的权值之和。且定义大集合的权值为小集合的权值之积，那么式子仍然适用。上面的是权值全为1的特殊情况。