[loj6737]指数公式

你有一个正整数集合

$S$ ，现在请你回答对于

$1 \leq k \leq n$ ，有多少种将编号为

$1 \sim k$ 的球放入一些盒子的方案，使得每个盒子里球的数量都属于

$S$ 。你只想知道答案的奇偶性。

输入格式

共一行，包含一个长度为

$n$ 的

$\texttt 0/\texttt 1$ 串 (

$1 \leq n \leq 2 \times 10^6$ )，其中第

$i$ 位为

$1$ 当且仅当

$i \in S$ 。

输出格式

输出一行，包含一个长度为

$n$ 的

$\texttt 0/\texttt 1$ 串，其中第

$i$ 位表示

$k = i$ 时的答案模

$2$ 的值。

题解

对于基础的球和盒子的问题，考虑建立生成函数模型。根据题意，这是一个有标号无序组，

记指数生成函数

$\displaystyle f \left( x \right) = \sum_{i \in S} \frac {x^i} {i !}$ ，则答案的指数生成函数即为

$g \left( x \right) = \exp f \left( x \right)$ 。

不过这里的问题是整个运算需要在模

$2$ 下进行，也就是说这些阶乘分母可能不存在。

也就是说数域为

$\mathbb F_2$ 。根据 [soj1006]Nimber Exp 的经验，在特征为

$2$ 的域上做多项式

$\exp$ ，可以通过对分子进行子集卷积得到二项卷积，而一个常数项为

$1$ 的生成函数的二项卷积逆为其本身。

因此可以像那道题一样进行 Newton 迭代，在

$O \left( n \log^2 n \right)$ 时间内得到答案。

不过，这道题由于数域仅为

$\mathbb F_2$ 而不是

$\mathbb F_{2^{32}}$ ，因此可以使用类似压位的思想来 "去掉一个

$\log$ "，从而才能跑

$2^{21}$ 。

事实上，在子集卷积的时候，我们可以将占位多项式压缩到一个

$32$ 位整数中存储，然后两个

$32$ 位整数的 "多项式乘法" 显然可以在

$O \left( \log n \right)$ 时间内完成 (可以参考这里)。

于是总时间复杂度即为

$O \left( n \log n \right)$ ，或更严谨地，

$O \left( \dfrac {n \log^2 n} \omega \right)$ 。

代码

#include <bits/stdc++.h>
#define popc __builtin_popcount
#define parity __builtin_parity
#define lg2 std::__lg
#define ctz __builtin_ctz
using std::cin;
using std::cout;

typedef unsigned short u16;
typedef unsigned int u32;
const int N = 65540;
typedef u32 vec[N], *pvec;

namespace bin {
	const u32 mask[32] = {
		0x00000001u, 0x00000003u, 0x00000005u, 0x0000000fu,
		0x00000011u, 0x00000033u, 0x00000055u, 0x000000ffu,
		0x00000101u, 0x00000303u, 0x00000505u, 0x00000f0fu,
		0x00001111u, 0x00003333u, 0x00005555u, 0x0000ffffu,
		0x00010001u, 0x00030003u, 0x00050005u, 0x000f000fu,
		0x00110011u, 0x00330033u, 0x00550055u, 0x00ff00ffu,
		0x01010101u, 0x03030303u, 0x05050505u, 0x0f0f0f0fu,
		0x11111111u, 0x33333333u, 0x55555555u, 0xffffffffu
	};

	u16 revi[65536];

	void init() {for (int i = 1; i < 65536; ++i) revi[i] = revi[i >> 1] >> 1 | (i & 1) << 15;}

	inline u32 rev(u32 x) {return revi[x >> 16] | revi[x & 65535u] << 16;}
}

namespace poly {
	int l, n;
	vec B1;
	u32 M1[N << 5], M2[N << 5];

	u32 exp_unit(u32 x) {
		assert(!(x & 1)), x = bin::rev(x);
		int i; u32 y = 1;
		for (i = 1; i < 32; ++i) y |= (u32)parity(x >> (31 - i) & y & bin::mask[i - 1]) << i;
		return y;
	}

	u32 conv_unit(u32 x, u32 y) {
		u32 z = 0;
		for (; x; x &= x - 1) z ^= y << ctz(x);
		return z;
	}

	inline void FMT_init(int len) {n = 1 << (l = len);}

	void FMT(pvec a) {
		int i, len = 1; u32 *j, *k;
		for (i = 0; i < l; ++i, len <<= 1)
			for (j = a; j != a + n; j += len << 1)
				for (k = j; k != j + len; ++k) k[len] ^= *k;
	}

	void FMT(pvec a, pvec b) {
		for (int i = 0; i < n; ++i) b[i] = (a[i >> 5] >> (i & 31) & 1) << popc(i);
		FMT(b);
	}

	void IFMT(pvec a, pvec b) {
		FMT(a);
		for (int i = 0; i < n; ++i) b[i >> 5] |= (a[i] >> popc(i) & 1) << (i & 31);
	}

	void exp(int deg, pvec a, pvec b) {
		int i, len, n;
		if (*b = exp_unit(*a), deg < 2) return;
		memset(b + 2, 0, i = 8 << lg2(deg - 1)), memset(B1, 0, i);
		for (len = 0, n = 1; n < deg; ++len, n <<= 1) {
			FMT_init(len + 5);
			memcpy(B1, a + n, n << 2), *B1 ^= (len ? b[n >> 1] : *b >> 16) & 1;
			FMT(B1, M1), FMT(b, M2);
			for (i = 0; i < n << 5; ++i) M1[i] = conv_unit(M1[i], M2[i]);
			IFMT(M1, b + n);
		}
	}
}

int n;
vec f, g;
char s[N << 5];

int main() {
	int i, L; bin::init();
	cin >> (s + 1), L = strlen(s + 1), n = L >> 5;
	for (i = 1; i <= L; ++i) f[i >> 5] |= u32(s[i] & 1) << (i & 31);
	poly::exp(n + 1, f, g);
	for (i = 1; i <= L; ++i) s[i] = (g[i >> 5] >> (i & 31) & 1) | 48;
	cout << s + 1 << '\n';
	return 0;
}

坑

坑1：由于我们对多项式进行了压位，因此 Newton 迭代初始时可以直接预处理

$32$ 项，在这一部分可以通过递推公式及掩码快速与处理。

坑2：注意两个压位多项式的 "卷积" 需要用到的操作是异或 (^)，而不是或 (|) 等 (第

$47$ 行)。

题目描述

输入格式

输出格式

题解

代码

坑