EI 的炫酷集合幂级数复合多项式魔法

对于任意的 nn 元集合上的一个集族对应的集合幂级数 AA 和 nn 次多项式 F(x)=∑i=0nfixiF(x)=\sum_{i=0}^nf_ix^i，可以在 O(2nn2)O(2^nn^2) 时间内计算：

∑i=0nfiAi\sum_{i=0}^nf_iA^i

其中 AiA^i 代表 ii 个 AA 做子集卷积。

考虑一般的子集卷积 exp。在那里我们的做法是按最高位分为 nn 组，这样每组只有一个。不妨沿用这个思路。

但是做 exp 的时候，子集个数上面带的 (i!)−1(i!)^{-1} 系数被分组之后的固定顺序自然消去，现在无法自然消去。原来的做法中，GiG_i 代表前 ii 组分别构成的集合幂级数做子集卷积之后得到的集合幂级数。考虑一个暴力的推广，就是在外面枚举 AA 的次数 jj，然后在 GG 中再引入一个 kk 代表当前的卷积次数。转移的时候枚举是否往里乘就可以了。

这个非常好理解，但是无法达到 O(2nn2)O(2^nn^2) 的目标复杂度。

考虑一个优化。在暴力做法中，最后的答案是 ∑jGn,j,j\sum_j G_{n,j,j}，初始值是 G0,j,0=fj⋅j!G_{0,j,0}=f_j\cdot j!（由于固定顺序会自然消去 j!j!，这里要补回来），所以我们不妨将 kk 变为差值，即还剩多少次。答案就会变成 ∑jGn,j,0\sum_j G_{n,j,0}，初始状态是 G0,j,j=fj⋅j!G_{0,j,j}=f_j\cdot j!。

似乎没有卵用。

考虑类似于 zjoi 线段树里面的整体 DP 的思路，这里如果将 AA 视为常量、FF 视为变量，那么容易发现这个 DP 过程是线性的，所以就可以直接强行把 jj 一维加起来。

于是经过上述优化过程，我们得到了最终的 Elegia’s magic：

设 G0,i=fi×i!G_{0,i}=f_i\times i!。

不断进行两种转移：

  • Gi,j→Gi+1,jG_{i,j}\rightarrow G_{i+1,j}。（不卷第 ii 组）
  • Gi,j×Fi→Gi+1,j−1G_{i,j}\times F_i\rightarrow G_{i+1,j-1}。（卷第 ii 组）

最终答案为 Gn,0G_{n,0}。

复杂度：对于 Gi→Gi+1G_i\rightarrow G_{i+1} 转移的复杂度是 O((n−i)⋅2ii2)O((n-i)\cdot 2^ii^2)（前半部分是 jj 的个数，后半部分是子集卷积）。记 T(n)=∑2ii2(n−i)T(n)=\sum2^ii^2(n-i)，有 T(n)=T(n−1)+O(∑i=0n2ii2)=T(n−1)+O(2nn2)T(n)=T(n-1)+O(\sum_{i=0}^n2^ii^2)=T(n-1)+O(2^nn^2)。所以 T(n)=O(∑i=0n2ii2)=O(2nn2)T(n)=O(\sum_{i=0}^n2^ii^2)=O(2^nn^2)。

例. LOJ #154

模板题，多项式是 F(x)=∑i=0kxii!F(x)=\displaystyle\sum_{i=0}^k\dfrac{x^i}{i!}，AA 就是题里面给你那 mm 个东西，直接套复合即可。

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
#include <bits/stdc++.h>
using namespace std;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int qread() {
	register char c = getchar();
	register int x = 0, f = 1;
	while (c < '0' || c > '9') {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + c - 48;
		c = getchar();
	}
	return x * f;
}

const long long mod = 998244353;
int n, m, k;
vector <int> f[22];
int g[22][1 << 21], ffwt[22][1 << 21], gfwt[22][1 << 21], h[1 << 21];

inline int Add(int x, int y) {
	return (x + y >= mod ? x + y - mod : x + y);
}

inline int Minus(int x, int y) {
	return (x < y ? x - y + mod : x - y);
}

inline void Read() {
	n = qread(); m = qread(); k = qread();
	for (int i = 1;i <= m;i++) {
		int x = qread();
		for (int j = n - 1;j >= 0;j--) {
			if ((x >> j) & 1) {
				f[j].push_back(x);
				break;
			}
		}
	}
}

inline void FWT(int *f, int w) {
	for (int i = 0;i < w;i++) {
		for (int j = 0;j < (1 << w);j += (1 << i + 1)) {
			for (int k = j;k < j + (1 << i);k++) f[k + (1 << i)] = Add(f[k + (1 << i)], f[k]);
		}
	}
}

inline void IFWT(int *f, int w) {
	for (int i = 0;i < w;i++) {
		for (int j = 0;j < (1 << w);j += (1 << i + 1)) {
			for (int k = j;k < j + (1 << i);k++) f[k + (1 << i)] = Minus(f[k + (1 << i)], f[k]);
		}
	}
}

inline void Solve() {
	for (int i = 0;i <= k;i++) g[i][0] = 1;
	for (int i = 1;i <= n;i++) {
		for (int j = 0;j <= i;j++) {
			for (int k = 0;k < (1 << i);k++) ffwt[j][k] = 0;
		}
		for (int j = 0;j < f[i - 1].size();j++) ffwt[__builtin_popcount(f[i - 1][j])][f[i - 1][j]]++;
		for (int j = 0;j <= i;j++) FWT(ffwt[j], i);
		for (int j = 0;j <= n - i;j++) {
			for (int j = 0;j <= i;j++) {
				for (int k = 0;k < (1 << i);k++) gfwt[j][k] = 0;
			}
			for (int k = 0;k < (1 << i);k++) gfwt[__builtin_popcount(k)][k] = Add(gfwt[__builtin_popcount(k)][k], g[j + 1][k]);
			for (int k = 0;k <= i;k++) FWT(gfwt[k], i);
			for (int k = 0;k <= i;k++) {
				for (int t = 0;t < (1 << i);t++) h[t] = 0;
				for (int l = 0;l <= k;l++) {
					for (int t = 0;t < (1 << i);t++) h[t] = Add(h[t], 1ll * ffwt[l][t] * gfwt[k - l][t] % mod);
				}
				IFWT(h, i);
				for (int t = 0;t < (1 << i);t++) {
					if (__builtin_popcount(t) == k) g[j][t] = Add(g[j][t], h[t]);
				}
			}
		}
	}
	cout << g[0][(1 << n) - 1] << endl;
}

int main() {
	Read();
	Solve();
	#ifdef CFA_44
	while (1);
	#endif
	return 0;
}

例. Jisuanke T3861

官方题解居然是个 O(Nlog⁡23log⁡N)O(N^{\log_23}\log N) 卡常，难蚌。

首先考虑这个博弈：对于一个字符串 ss，设每个字符分别出现了 a1,a2,⋯ ,aka_1,a_2,\cdots,a_k 次，那么对应到有向图博弈上面，重排字符串相当于在一条长度为 n!∏ai!\dfrac{n!}{\prod a_i!} 的链上移动一步，而删一个字符 ii 相当于移动到一条长度为 (n−1)!(ai−1)!∏j≠iaj!\dfrac{(n-1)!}{(a_i-1)!\prod_{j\neq i} a_j!} 的链的链头。

考虑分析每一个点是必胜/必败点。如果存在一条能走到的链，它的链头是必败点，那么链上所有点都是必胜点；否则链尾是必败点，剩下的点按顺序交错是必胜/必败。

可以得到结论 1：长度为偶数的链的链头一定必胜。推论：任何一个人不会尝试走到一个长度为偶数的链的链头。

结论 2：长度为奇数的链一定可以走到另一个长度为奇数的链头。

证明：考虑链长是 n!∏ai!\dfrac{n!}{\prod a_i!} 其中 ∑ai=n\sum a_i=n，移动之后链长乘上 ain\dfrac{a_i}{n}，只需证明存在一个 aia_i 和 nn 含的 2 因子个数恰好一样多即可。

首先一定存在一个 aia_i 含的 2 因子个数小于等于 nn 含的 2 因子个数，否则 nn 含更多 2 因子。

如果存在一个 aia_i 含的 2 因子个数小于 nn 含的 2 因子个数，那么 ain\dfrac{a_i}{n} 化为有理分式之后分子是奇数，分母是偶数；同时 n!∏ai!×ain=(n−1)!(ai−1)!∏j≠iaj!\dfrac{n!}{\prod a_i!}\times \dfrac{a_i}{n}=\dfrac{(n-1)!}{(a_i-1)!\prod_{j\neq i} a_j!} 是整数，即 n!∏ai!\dfrac{n!}{\prod a_i!} 是偶数，矛盾。

归纳易证初始链长是奇数时，链头是必败点当且仅当 nn 是偶数。

于是 nn 为奇数时答案为 knk^n。

当 nn 为偶数时，我们需要统计的是有多少种 a1,a2,⋯ ,aka_1,a_2,\cdots,a_k 使得 ∑ai=n\sum a_i=n 且 n!∏ai!\dfrac{n!}{\prod a_i!} 是奇数。类似结论 2 的证明分析，容易得到 n!∏ai!\dfrac{n!}{\prod a_i!} 是奇数的充要条件是求 ∑ai\sum a_i 时在二进制下不发生进位。

于是我们可以在二进制下把 nn 看成一个 {0,1,⋯ ,⌈log⁡2n⌉−1}\{0,1,\cdots,\lceil\log_2n\rceil-1\} 的子集 SS，问题转化为求所有将 SS 划分为若干子集 T1,T2,⋯ ,TmT_1,T_2,\cdots,T_m 的方式的权值之和，一个方式的权值是：

km‾⋅n!∏i=1m(∑u∈Ti2u)!k^{\underline{m}}\cdot\dfrac{n!}{\prod_{i=1}^m(\sum_{u\in T_i}2^u)!}

写成集合幂级数的形式：

A(x)=∑T⊆SxT(∑u∈T2u)!A(x)=\sum_{T\subseteq S}\dfrac{x^T}{(\sum_{u\in T}2^u)!}

所求为：

[xS]∑i=1∣S∣ki‾Ai[x^S]\sum_{i=1}^{|S|}k^{\underline{i}}A^i

使用上述复合算法即可 O(Nlog⁡2N)O(N\log^2N) 求解。