P12230 集合幂级数 exp

· · 题解

怎么什么乱七八糟的东西都能丢到 e 的头上 .jpg

e^{F(x)} = \sum_{n \ge 0} \frac {F^n(x)} {n!}

不过盯着这个泰勒展开看你可以瞪出他的组合意义。套用 cxy 在 APIO 2025 的讲课 PPT 上的话说，将 [x^S] F(x) 视为划分出一个 S 的子集的权值，那么 [x^S] e^{F(x)} 表示 S 集合的所有划分方案（划分出的子集是无序的）的权值和，一种划分方案的权值定义为划分出的所有子集的权值之积。

能够理解的是我们不能选择空集，否则方案数是不是就无穷多个了，即钦定 [x^{\varnothing}]F(x) = 0。同样的，[x^\varnothing] e^{F(x)} = 1。

一般来说，有两种 O(2^n n^2) 的算法求集合幂级数 \exp。

算法一

这个算法要求 1 \sim n 存在逆元，无法通过加强版。

考虑子集卷积的类似套路。添加辅助元 y，设 [x^S y^i] F(x, y) = [x^S] F(x) \times [\lvert S \rvert = i]。

定义这个幂级数的 \operatorname{exp}，

e^{F(x, y)} = \sum_{n \ge 0} \frac {F^n(x, y)} {n!}

其中 F(x, y) 的乘法 x 维上是集合并卷积，y 维上是和卷积。即由 x^S y^i 和 x^T y^j 贡献到 x^{S \cup T} y^{i + j}。

两维独立，固定 y 的次数，在 x 维上 FMT，之后相当于是从 x^S y^i 和 x^S y^j 贡献到 x^S y^{i + j}。

现在对于每个不同的 S 也是独立的，只需要 O(2^n) 次求出一个关于 y 的 n 次多项式的 \exp。

你当然可以拉 O(n \log n) 求多项式 \exp 的板子。 但我们有 O(n^2) 的算法。

设 f(y) 是一个关于 y 的 n 次多项式，设 g(y) = e^{f(y)}。

求导可得 g'(y) = e^{f(y)} f'(y) = g(y) \times f'(y)。

[y^n] g'(y) & = \sum_{i = 0}^n [y^{n-i}] g(y) \times [y^i] f'(y) \\ (n + 1) [y^{n+1}] g(y) & = \sum_{i = 0}^{n} [y^{n-i}] g(y) \times (i + 1) [y^{i+1}] f(y)\\ [y^{n}] g(y) & = \frac 1 n \sum_{i = 1}^{n} [y^{n-i}] g(y) \times i [y^i] f(y) \\ \end{aligned}

直接递推便是 O(n^2) 的。

求 O(2^n) 次多项式 \exp，做 O(n) 次 FMT 或 IFMT，复杂度都是 O(2^n n^2)。

:::info[代码]

#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int N = 21, K = 1 << N;
const int P = 998244353;

int n, pcnt[K], f[N][K], g[N][K];

int qPow(int x, int y) {
  int res = 1;
  for (; y; x = 1ll * x * x % P, y >>= 1)
    if (y & 1) res = 1ll * res * x % P;
  return res;
}
void Add(int &x, int y) { x += y; if (x >= P) x -= P; }
void FMT(int *f, int tp) {
  F(i, 0, n - 1) F(j, 0, (1 << n) - 1)
    if (j >> i & 1)
      if (tp > 0) Add(f[j], f[j ^ 1 << i]);
      else Add(f[j], P - f[j ^ 1 << i]);
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  F(i, 1, (1 << n) - 1) pcnt[i] = pcnt[i ^ (i & -i)] + 1;
  F(i, 0, (1 << n) - 1) cin >> f[pcnt[i]][i];
  F(i, 0, n) FMT(f[i], 1);
  F(i, 0, (1 << n) - 1) g[0][i] = 1;
  F(i, 1, n) {
    F(j, 1, i) F(k, 0, (1 << n) - 1)
      Add(g[i][k], 1ll * g[i - j][k] * f[j][k] % P * j % P);
    int iv = qPow(i, P - 2);
    F(j, 0, (1 << n) - 1) g[i][j] = 1ll * g[i][j] * iv % P;
  }
  F(i, 0, n) FMT(g[i], -1);
  F(i, 0, (1 << n) - 1) cout << g[pcnt[i]][i] << " ";
  return 0;
}

:::

算法二

这个算法不需要用到逆元，可以通过加强版。

对着组合意义做有一个简单做法。由于划分集合无序，不妨钦定一个枚举顺序。设 S 的最大元为 u，枚举其所在的小集合 T，则

[x^S] e^{F(x)} = \sum_{u \in T, T \subseteq S} [x^T] F(x) \times [x^{S \setminus T}] e^{F(x)}

考虑从小到大枚举 u。设 S \setminus \{u\} = S_0，T \setminus \{u\} = T_0。利用上式从 [x^{S_0}] F(x) 推到 [x^S] F(x)。

这个东西每次做子集卷积就可以了。因为实际上是枚举 T_0 和 S_0 \setminus T_0，然后将 [x^{\{u\} \cup T_0}] F(x) \times [x^{S_0 \setminus T_0}] e^{F(x)} 贡献到 [x^{\{u\} \cup S_0}] e^{F(x)} 上。u 这个东西相当于是不用管它，代码里数组整体移位 2^{u-1}。

时间复杂度是 T(n) = T(n - 1) + O(2^n n^2) = O(2^n n^2)。

:::info[代码]

#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int N = 20, K = 1 << N;

int n, pcnt[K]; ull f[N + 1][K], g[N + 1][K];

void FMT(ull *f, int n, ull tp) {
  F(i, 0, n - 1) F(j, 0, (1 << n) - 1)
    if (j >> i & 1) f[j] += tp * f[j ^ 1 << i];
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  F(i, 1, (1 << n) - 1) pcnt[i] = pcnt[i ^ (i & -i)] + 1;
  F(i, 0, (1 << n) - 1) cin >> f[pcnt[i]][i];
  g[0][0] = 1;
  F(u, 1, n) {
    int cur = (1 << u - 1);
    F(i, 1, u) FMT(f[i] + cur, u - 1, 1ull);
    F(i, 0, u - 1) FMT(g[i], u - 1, 1ull);
    F(i, 1, u) F(j, 0, u - i)
      F(k, 0, (1 << u - 1) - 1)
        g[i + j][k + cur] += f[i][k + cur] * g[j][k];
    F(i, 0, u - 1) FMT(g[i], u - 1, -1ull);
    F(i, 1, u) FMT(g[i] + cur, u - 1, -1ull);
  }
  F(i, 0, (1 << n) - 1) cout << g[pcnt[i]][i] << " ";
  return 0;
}

:::

集合幂级数 \exp 的技术在一些生成子图相关的计数题中有大量运用。

比如几个经典的正式赛题，我不说是什么。