小 Q 和小 Y 都是图论带师，祂们特别喜欢完全图。
对于一张图，如果它的每个连通块都是完全图，那么这张图是小 Q 和小 Y 所喜欢的，否则不喜欢。
现在，小 Q 和小 Y 在一些喜欢的图上做游戏。
最开始时，每张图上大小为 $i$ 的连通块上写着一个整数 $f_i$。
在一个人操作时，首先选择一张图，满足这张图的每个连通块上写的数都是正整数。如果没有这样的图则当前操作者失败。
对于每个连通块，选择一个比原来的数更小的非负整数。
对于每个连通块集合的非空子集，在图的集合中添加一张选择图的拷贝，并把这张图在子集中的连通块上数改为新选择的数。
将选择的图从图的集合中删去，并由另一个人从步骤 2 开始操作。
不难证明游戏的过程是有限的。
现在，小 Q 和小 Y 在所有喜欢的顶点数为 $m$ 的 (有标号) 图进行上面的游戏，小 Q 先手。
由于小 Y 非常希望胜利，所以祂准备作弊。由于一些原因，祂只能修改 $f_m$ 的值。
于是小 Y 准备寻求你的帮助，希望你求出，对于 $m = 1, 2, \cdots, n$，分别应该把 $f_m$ 改成多少才能使得祂必胜。
第一行包含一个正整数 $n$ ($n \leq 2 \times 10^5$)，表示图的点数的上限。
第二行包含 $n$ 个非负整数 $f_1, f_2, \cdots, f_n$ ($0 \leq f_i < 2^{32}$)，依次表示各个大小的连通块上初始该写的整数。
输出一行，包含 $n$ 个非负整数，其中第 $m$ 个整数表示只能修改 $f_m$ 时，应该把 $f_m$ 改成多少才能使小 Y 必胜。可以证明这样的数是唯一的。
不难发现题中所给的模型是一个公平组合游戏，因此每个游戏均有一个 SG 值，考虑如何对其进行刻画。
对于一张确定的图，设连通块大小分别为 $s_1, s_2, \cdots, s_k$，那么它的 SG 值等于多少呢？
考虑一次操作，不难发现它其实可以看成 $k$ 维空间上一个坐标为 $\left( f_{s_1}, f_{s_2}, \cdots, f_{s_k} \right)$ 的白点，每次操作可以选择一个以它为 "右上角" 的 $k$ 维超 "长方体"，然后将这个长方体中的所有点的颜色翻转。
不难发现，这其实和 Nim 积的定义相吻合 —— 因此这个游戏的 SG 值就等于 $f_{s_1} \otimes f_{s_2} \otimes \cdots \otimes f_{s_k}$。
现在，考虑所有顶点数为 $m$ 的 (满足条件的) 图的和，那么，考虑到这样的图其实就是若干完全图的有标号无序组，因此我们可以考虑使用多项式 $\exp$。
具体地，设 $$ A \left( x \right) = f_1 x \oplus f_2 \frac {x^2} {2 !} \oplus f_3 \frac {x^3} {3 !} \oplus \cdots \oplus f_k \frac {x^k} {k !} \oplus \cdots $$ 则最终表示大小为 $i$ 的图的 SG 值的生成函数就等于 $$ \exp A \left( x \right) = 1 \oplus A \left( x \right) \oplus \frac {A^2 \left( x \right)} {2 !} \oplus \frac {A^3 \left( x \right)} {3 !} \oplus \cdots \oplus \frac { A^k \left( x \right)} {k !} \cdots = \bigoplus_{i \geq 0} \frac {A^i \left( x \right)} {i !} $$
但是，这里要注意的是，这个生成函数的系数其实都是 Nimber，换句话说就是在一个特征为 $2$ 的域上进行，因此实际上 $\dfrac {f_2} {2 !}$ 是一个不存在的数，也就是说我们不能直接按照上式进行计算。
这时，我们可以类比普通生成函数的微分和积分，得到：
设 $B \left( x \right) = \exp A \left( x \right)$，则 $B' \left( x \right) = B \left( x \right) \otimes A' \left( x \right)$。
此时，每一项 $x^i$ 的系数中还有分母 $\dfrac 1 {i !}$，如果我们将其中的分母去掉 (即每一项乘以 $i !$)，根据组合意义，所得到的系数就一定是整数了。
为了方便起见，我们可以记 $\displaystyle A \left( x \right) = \bigoplus_{i \geq 1} f_i \frac {x^i} {i !}, B \left( x \right) = \bigoplus_{i \geq 0} g_i \frac {x^i} {i !}$。
这样我们就将一般的卷积 "还原" 成了最基础的二项卷积。考虑一般的技巧，两边求 $x^n$ 项系数，就能得到：$$ g_{n+1} = \bigoplus_{i=0}^n \binom ni \cdot \left( f_{i+1} \otimes g_{n-i} \right) $$ (其中 $\cdot$ 表示数乘，即 $\lambda \cdot x = \underbrace {x \oplus x \oplus \cdots \oplus x}_{\lambda \text{ 个}}$)
并注意到 $\dbinom {a + b} a \equiv \left[ a \mathbin{\&} b = 0 \right] \pmod 2$，因此二项卷积实质上就是子集卷积。于是这样就可以在 $O \left( n^{\log_2 3} \right)$ 时间内完成计算。
当然，现在我们只是会计算 $\exp$，而这并不是答案。我们所要的答案是将 $f_m$ 修改为多少时才能使得 $g_m = 0$。
首先，设将 $f_m$ 修改为了 $w$。注意到修改 $f_m$ 并不会影响 $g_0, g_1, \cdots, g_{m-1}$，因此新的 $$ g'_m = \bigoplus_{i=0}^{m-1} \binom mi \cdot \left( f'_{i+1} \otimes g_{m-1-i} \right) = \bigoplus_{i=0}^{m-1} \binom mi \cdot \left( f_{i+1} \otimes g_{m-1-i} \right) \oplus \binom m0 \cdot \left( \left( f_m \oplus w \right) \otimes 1 \right) = g_m \oplus f_m \oplus w $$
而我们希望 $g'_m = 0$，因此需要 $w = g_m \oplus f_m$，而我们已经求出 $g$ 数组，因此问题得到解决。
下面考虑如何快速地计算 $\exp$。以下假设 Nim 积 ($2^{32}$ 内，即有限域 $\mathbb F_{2^{32}}$ 中的乘法) 计算的时间复杂度为 $O \left( 1 \right)$。
我们用符号 $\circledast$ 表示两个序列 (一般生成函数) 的二项卷积 (子集卷积)。那么，容易证明对于任意生成函数 $f \left( x \right)$，若 $f$ 的常数项 $\left[ x^0 \right] f \left( x \right) = c$，则 $f \circledast f = c \otimes c$，即它只有常数项。
于是，可以得到一个重要的推论：一个常数项为 $1$ 的生成函数的二项卷积逆为其本身。
现在考虑 $g \left( x \right) = \exp f \left( x \right) \Rightarrow g' \left( x \right) = g \left( x \right) \circledast f' \left( x \right)$，这里约定 $\left[ x^0 \right] f \left( x \right) = 0, \left[ x^0 \right] g \left( x \right) = 1$。
于是，两边乘 $g \left( x \right)$ 得 $f' \left( x \right) = g' \left( x \right) \circledast g \left( x \right)$，于是通过 $g$ 求 $f$ (即求对数) 可以通过一次子集卷积得到，时间复杂度 $O \left( n \log^2 n \right)$。
根据一般模意义下的生成函数的套路，(在这里显然不能分治) 如果可以求 $\ln$，那么求 $\exp$ 只需在外层套一个 Newton 迭代：$$ g_{2 k} \left( x \right) = g_k \left( x \right) \circledast \left( 1 \oplus \ln g_k \left( x \right) \oplus f \left( x \right) \right) $$
于是时间复杂度 $O \left( n \log^2 n \right)$。(ps: 当然，可以通过更精细地分析，可以将一轮迭代中的 FMT 次数降到 $3$ 次，从而得到更快的写法，具体见下方代码)
#include <bits/stdc++.h>
#define popc __builtin_popcount
#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 = 265000;
typedef u32 vec[N], *pvec;
namespace nimbers {
constexpr u32 n2f[16] = {0x0001u, 0x8ff5u, 0x6cbfu, 0xa5beu, 0x761au, 0x8238u, 0x4f08u, 0x95acu, 0xf340u, 0x1336u, 0x7d5eu, 0x86e7u, 0x3a47u, 0xe796u, 0xb7c3u, 0x0008u},
f2n[16] = {0x0001u, 0x2827u, 0x392bu, 0x8000u, 0x20fdu, 0x4d1du, 0xde4au, 0x0a17u, 0x3464u, 0xe3a9u, 0x6d8du, 0x34bcu, 0xa921u, 0xa173u, 0x0ebcu, 0x0e69u};
inline u32 nimber2field(u32 x) {u32 y = 0; for (; x; x &= x - 1) y ^= n2f[ctz(x)]; return y;}
inline u32 field2nimber(u32 x) {u32 y = 0; for (; x; x &= x - 1) y ^= f2n[ctz(x)]; return y;}
inline u32 __builtin_double(u32 x) {return x << 1 ^ (x < 0x8000u ? 0 : 0x1681fu);}
u16 ln[65536], exp[131075], *Hexp = exp + 3, *H2exp = exp + 6;
inline void init() {
int i;
for (*exp = i = 1; i < 65535; ++i) exp[i] = __builtin_double(exp[i - 1]);
for (i = 1; i < 65535; ++i) exp[i] = field2nimber(exp[i]), ln[exp[i]] = i;
memcpy(exp + 65535, exp, 131070);
memcpy(exp + 131070, exp, 10);
}
inline u16 product(u16 A, u16 B) {return A && B ? exp[ln[A] + ln[B]] : 0;}
inline u16 H(u16 A) {return A ? Hexp[ln[A]] : 0;}
inline u16 H2(u16 A) {return A ? H2exp[ln[A]] : 0;}
inline u16 Hproduct(u16 A, u16 B) {return A && B ? Hexp[ln[A] + ln[B]] : 0;}
inline u32 product(u32 A, u32 B) {
u16 a = A & 65535, b = B & 65535, c = A >> 16, d = B >> 16, e = product(a, b);
return u32(product(u16(a ^ c), u16(b ^ d)) ^ e) << 16 | (Hproduct(c, d) ^ e);
}
inline u32 H(u32 A) {
u16 a = A & 65535, b = A >> 16;
return H(u16(a ^ b)) << 16 | H2(b);
}
}
namespace fmt {
int l, n;
typedef u32 mat[N][19], (*pmat)[19];
inline void FMT_init(int len) {n = 1 << (l = len);}
inline void addVec(u32 *a, u32 *b) {for (int i = 0; i <= l; ++i) a[i] ^= b[i];}
inline void mulVec(u32 *a, u32 *b) {
int i, j;
static u32 u[N];
for (i = 0; i <= l; ++i)
for (u[i] = j = 0; j <= i; ++j)
u[i] ^= nimbers::product(a[j], b[i - j]);
memcpy(a, u, (l + 1) << 2);
}
void FMT(pmat a) {
int i, len = 1; pmat 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)
addVec(k[len], *k);
}
inline void FMT(pvec a, pmat b) {
for (int i = 0; i < n; ++i) memset(b[i], 0, l << 2), b[i][popc(i)] = a[i];
FMT(b);
}
inline void IFMT(pmat a, pvec b) {
FMT(a);
for (int i = 0; i < n; ++i) b[i] = a[i][popc(i)];
}
}
namespace gfpoly {
using namespace fmt;
vec B1;
mat M1, M2;
void exp(int deg, pvec a, pvec b) {
int i, len; assert(!*a);
if (*b = 1, deg <= 1) return;
if (b[1] = a[1], deg == 2) return;
memset(b + 2, 0, i = 8 << lg2(deg - 1)), memset(B1, 0, i);
for (len = 1; 1 << len < deg; ++len) {
FMT_init(len),
memcpy(B1, a + n, n << 2), *B1 ^= nimbers::product(b[n >> 1], b[n >> 1]),
FMT(B1, M1), FMT(b, M2);
for (i = 0; i < n; ++i) mulVec(M1[i], M2[i]);
IFMT(M1, b + n);
}
}
}
int n;
vec f, g;
int main() {
int i; nimbers::init();
cin >> n;
for (i = 1; i <= n; ++i) cin >> f[i];
gfpoly::exp(n + 1, f, g);
for (i = 1; i <= n; ++i) cout << (f[i] ^ g[i]) << (i == n ? '\n' : ' ');
return 0;
}
坑1：在 FMT 的时候由于需要占位多项式 (是二维数组)，因此 FMT 之前别忘了清空上次的数组。
坑2：在计算 Nim 积的时候，可以通过存储 $2^{16}$ 以内的指数对数表，又由于中间需要一个乘 $32768$ 的运算，因此我们可以合适地选择原根 (如 $10279$) 使得 $32768$ 的离散对数尽可能地小。