黎明前的巧克力 / CF1906K Deck-Building Game

注意到原题方案数相当于选择一个异或和为 00 的子集 SS 并乘上 2∣S∣2^{|S|} 的系数。那么可以列出答案柿子为：

[x0]∏i=1n(1+2xai)[x^0] \prod_{i = 1}^n (1 + 2x^{a_i})

这可以使用类似分治 NTT 的东西来做到 O(n+m22m)\mathcal{O}(n + m^22^m)，具体来讲就是分别只保留最高位为 00 或 11 的部分递归下去，然后使用这两部分的结果分别合并出最后异或出来时最高位为 00 或 11 的结果。这样做时间复杂度正确的原理在于，如果设值域为 2m2^m，且确定了长度为 kk 的前缀，那么这些东西只能异或出 O(2m−k)\mathcal{O}(2^{m - k}) 种结果。

但是我们也许可以做到更优。考虑求出这个东西 FWT 之后的结果，再 IFWT 回去：

[xk]FWT⁡(∏i=1n(1+2xai))[x^k] \operatorname{FWT}\left(\prod_{i = 1}^n (1 + 2x^{a_i})\right)

我们直接去考虑更加一般的情况：对于每个 kk，我们都需要求出：（这里的 aia_i 和前面的 aia_i 意义不同）

[xk]FWT⁡(∏i=1n(ai+bixci))[x^k] \operatorname{FWT}\left(\prod_{i = 1}^n (a_i + b_ix^{c_i})\right)

然后我们发现，(ai+bixic)(di+eixic)=aidi+biei+(aiei+bidi)xc(a_i + b_ix^c_i)(d_i + e_ix^c_i) = a_id_i + b_ie_i + (a_ie_i + b_id_i) x^c，这样我们可以将所有 cic_i 相同的东西合并到一起，那么问题变成了：

[xk]FWT⁡(∏i=02m−1(ai+bixi))=∏i=02m−1[xk]FWT⁡(ai+bixi)=∏i=02m−1(ai+bi(−1)∣k∩i∣)\begin{aligned} & [x^k] \operatorname{FWT}\left(\prod_{i = 0}^{2^m - 1} (a_i + b_ix^i)\right)\\ = & \prod_{i = 0}^{2^m - 1} [x^k] \operatorname{FWT}(a_i + b_ix^i)\\ = & \prod_{i = 0}^{2^m - 1} (a_i + b_i(-1)^{|k \cap i|}) \end{aligned}

我们再额外记录一个 ∏(ai−bi(−1)∣k∩i∣)\prod (a_i - b_i(-1)^{|k \cap i|}) 即可使用类似一般异或 FWT 的方法来互相转移，从而做到 O(n+m2m)\mathcal{O}(n + m2^m)。

CF1119H Triple

这个题显然是上一个题中项数从 22 拓展为 33 的情况。发现并无法直接从上一题的做法拓展过来，于是可能需要关注一些在上一题中被我们忽略掉的性质，比如每一项内部的系数都是相同的 X,Y,ZX, Y, Z。仍然考虑问题的一般化形式，假设我们需要对于每个 ii 都求出：

[xi]FWT⁡(∏j=1n∑p=1kwpxaj,p)=∏j=1n[xi]FWT⁡(∑p=1kwpxaj,p)=∏j=1n∑p=1kwp(−1)∣aj,p∩i∣\begin{aligned} & [x^i] \operatorname{FWT}\left(\prod_{j = 1}^n \sum_{p = 1}^k w_p x^{a_{j, p}}\right)\\ = & \prod_{j = 1}^n [x^i] \operatorname{FWT}\left(\sum_{p = 1}^k w_p x^{a_{j, p}}\right)\\ = & \prod_{j = 1}^n \sum_{p = 1}^k w_p (-1)^{|a_{j, p} \cap i|}\\ \end{aligned}

注意到乘积的每一项只有 2k2^k 种取值，所以我们只需要关心每一种取值有多少个 jj 可以取到即可。对于每个 ii，令 ss 为一个 kk 位二进制数，设 csc_s 为：对于所有的 1≤p≤k1 \le p \le k，若 ss 的第 pp 位为 00，wpw_p 贡献系数为 11，否则为 −1-1，符合这样的贡献形式的 jj 的个数。

我们设 smj,s=⨁p∈saj,psm_{j, s} = \bigoplus_{p \in s} a_{j, p}，接着定义 hs=[xi]FWT⁡(∑j=1nxsmj,s)h_s = [x^i] \operatorname{FWT}\left(\sum_{j = 1}^n x^{sm_{j, s}}\right)，则有：

hs=[xi]FWT⁡(∑j=1nxsmj,s)=∑j=1n[xi]FWT⁡(∏p∈sxaj,p)=∑j=1n∏p∈s[xi]FWT⁡(xaj,p)=∑j=1n∏p∈s(−1)∣aj,p∩i∣=∑t=02k−1ct(−1)∣s∩t∣\begin{aligned} h_s=&[x^i] \operatorname{FWT}\left(\sum_{j = 1}^n x^{sm_{j, s}}\right)\\ =&\sum_{j = 1}^n [x^i]\operatorname{FWT}\left(\prod_{p \in s} x^{a_{j, p}}\right)\\ =&\sum_{j = 1}^n \prod_{p \in s} [x^i]\operatorname{FWT}(x^{a_{j, p}})\\ =&\sum_{j = 1}^n \prod_{p \in s} (-1)^{|a_{j, p} \cap i|}\\ =&\sum_{t = 0}^{2^k - 1} c_t(-1)^{|s \cap t|} \end{aligned}

对于最后一个等号是如何得到的，我们考虑一个 jj，若它被归类到 ctc_t 中，那么对于所有 pp，都有 [p∈t]=[(−1)∣aj,p∩i∣=−1][p \in t] = [(-1)^{|a_{j, p} \cap i|} = -1]。那么对于这样的 jj，∏p∈s(−1)∣aj,p∩i∣\prod_{p \in s} (-1)^{|a_{j, p} \cap i|} 中就会有 ∣s∩t∣|s \cap t| 个 −1-1。我们转而枚举 tt 即可得到最后的结果。

可以发现 hh 就是 cc 做一次 FWT 的结果，我们 IFWT 回去即可。最后我们对于每个 ii 都求出 ∏s=02k−1coscs\prod_{s = 0}^{2^k - 1} {co_s}^{c_s}，再做一遍 IFWT。

分析时间复杂度：求所有 smsm 需要 O(n2k)\mathcal{O}(n2^k)，求所有的 hh 需要 O(m2k+m)\mathcal{O}(m2^{k + m})，求所有的 cc 需要 O(k2k+m)\mathcal{O}(k2^{k + m})，预处理 cosco_s 的次方需要 O(n2k)\mathcal{O}(n2^k)，最后的 IFWT 需要 O(m2m)\mathcal{O}(m2^m)，综上所述，总时间复杂度为 O(n2k+(k+m)2k+m)\mathcal{O}(n2^k + (k + m)2^{k+m})。

ABC367G Sum of (XOR^K or 0)

我们直接考虑对于所有异或和求出对应序列的方案数，忽略这个 KK 次方。

这个题其实就是上一个题的 k=2k = 2 的情况（w1=1,w2=y,ai,1=0,ai,2=Aiw_1 = 1, w_2 = y, a_{i, 1} = 0, a_{i, 2} = A_i）。若我们直接套用上一题的做法，求 sm,h,csm, h, c 都不涉及到 yy，于是时间复杂度不变；预处理 cosco_s 的次方时需要记录 yy 相关的完整系数，每次需要乘上一个单项式，在本来 O(n2k)\mathcal{O}(n2^k) 的基础上多乘了一个 MM；求 ∏s=02k−1coscs\prod_{s = 0}^{2^k - 1} {co_s}^{c_s} 时涉及到了循环多项式的卷积，在本来 O(n2k)\mathcal{O}(n2^k) 的基础上多乘了两个 MM；最后 IFWT 回去的时候，只涉及到了 yy 相关的多项式的数乘与加减操作，所以只记录 y0y^0 的系数即可，时间复杂度不变。综上所述，总时间复杂度为 O(nM22k+mlog⁡K+(k+m)2k+m)\mathcal{O}(nM^22^k + m \log K + (k + m)2^{k+m})（如果你闲着没事干可以线性筛预处理 xKx^K 来去掉 log⁡\log）。

但是我们可以优化。由于所有的 aj,1=0a_{j, 1} = 0，所以 co0=co1,co2=co3co_0 = co_1, co_2 = co_3，而 ∏s=02k−1coscs\prod_{s = 0}^{2^k - 1} {co_s}^{c_s} 就可以写成 FpGqF^pG^q 的形式，且我们只关心这个东西 y0y^0 的系数，所以可以在预处理后 O(M)O(M) 计算。那么总时间复杂度变为 O(nM2k+mlog⁡K+(k+m)2k+m)\mathcal{O}(nM2^k + m \log K + (k + m)2^{k+m})，可以通过。

CF2096H Wonderful XOR Problem

在这题里，我们要求的是：

[xk]FWT⁡(∏i=1n∑j=lirixj)=∏i=1n[xk]FWT⁡(∑j=1rixj−∑j=1li−1xj)=∏i=1n([xk]FWT⁡(∑j=1rixj)−[xk]FWT⁡(∑j=1li−1xj))\begin{aligned} &[x^k] \operatorname{FWT}\left(\prod_{i = 1}^n \sum_{j = l_i}^{r_i} x^j\right)\\ =&\prod_{i = 1}^n [x^k] \operatorname{FWT}\left(\sum_{j = 1}^{r_i} x^j - \sum_{j = 1}^{l_i - 1} x^j\right)\\ =&\prod_{i = 1}^n \left([x^k] \operatorname{FWT}\left(\sum_{j = 1}^{r_i} x^j\right) - [x^k] \operatorname{FWT}\left(\sum_{j = 1}^{l_i - 1} x^j\right)\right)\\ \end{aligned}

我们设 f(r,i)f(r, i) 为 [xi]FWT⁡(∑j=1rxj)[x^i] \operatorname{FWT}\left(\sum_{j = 1}^r x^j\right)，那么我们要求的东西就变成了 ∏i=1n(f(ri,k)−f(li−1,k))\prod_{i = 1}^n (f(r_i, k) - f(l_i - 1, k))。考虑这个 f(r,i)f(r, i) 的性质：

f(r,i+2j+1)=f(r,i)f(2k−1,i)=2k[i mod 2k=0]f(r,i)={f(2j−1,i)+f(r−2j,i)i<2jf(2j−1,i)−f(r−2j,i)i≥2j (0≤i<2j+1)f(r,i)={r+1i=0f(r−2j,i)0<i<2j2j+1−r−1i=2j−f(r−2j,i)2j<i<2j+1 (0≤i<2j+1)f(r, i + 2^{j + 1}) = f(r, i)\\ f(2^k - 1, i) = 2^k[i \bmod 2^k = 0]\\ f(r, i) = \begin{cases} f(2^j - 1, i) + f(r - 2^j, i) & i < 2^j\\ f(2^j - 1, i) - f(r - 2^j, i) & i \ge 2^j\\ \end{cases} \ (0 \le i < 2^{j + 1})\\ f(r, i) = \begin{cases} r + 1 & i = 0\\ f(r - 2^j, i) & 0 < i < 2^j\\ 2^{j + 1} - r - 1 & i = 2^j\\ -f(r - 2^j, i) & 2^j < i < 2^{j+1}\\ \end{cases} \ (0 \le i < 2^{j + 1})\\

如果我们从高到低按位考虑，我们可以写出计算 f(r,i)f(r, i) 的代码：

inline int calc(int r, int i, int p = n - 1){
	if (!i) return r + 1;
	if (r >> p & 1 ^ 1){
		if (i >> p & 1) i ^= 1 << p;
		return calc(r, i, p - 1);
	}
	if (i == 1 << p) return (1 << p + 1) - r - 1;
	return i >> p & 1 ? -calc(r ^ 1 << p, i ^ 1 << p, p - 1) : calc(r ^ 1 << p, i, p - 1);
}

稍微进行一些观察，我们发现对于一个固定的 rr，f(r,i)f(r, i) 的绝对值只与 ii 的 lowbit 有关，而正负性是好求的，可以做到 O(1)\mathcal{O}(1)。

inline int calc(int r, int i){if (!i) return r + 1;
	int p = __builtin_ctz(i), neg = popc((r & i) >> p + 1) & 1 ? -1 : 1;
	if (r >> p & 1) return neg * ((1 << p + 1) - (r & (1 << p + 1) - 1) - 1);
	return neg * ((r & (1 << p) - 1) + 1);
}

考虑枚举 kk 的 lowbit 为 pp，即 kk 的第 pp 位为 11，更低位全为 00，更高位任意，将 lowbit 相同的 kk 放在一起算。

枚举 pp 后有 f(ri,k)=ai(−1)∣k′∩ri′∣f(r_i, k) = a_i(-1)^{|k' \cap r'_i|}，其中 aia_i 只与 rir_i 有关，k′=k/2p+1,ri′=ri/2p+1k' = k / 2^{p + 1}, r'_i = r_i / 2^{p + 1}，f(li−1,k)f(l_i - 1, k) 也是同理。那么我们所求的 ∏i=1n(f(ri,k)−f(li−1,k))\prod_{i = 1}^n (f(r_i, k) - f(l_i - 1, k)) 就转化成了 ∏i=1n(ai(−1)∣k′∩ci∣+bi(−1)∣k′∩di∣)\prod_{i = 1}^n (a_i(-1)^{|k' \cap c_i|} + b_i(-1)^{|k' \cap d_i|}) 的形式，而 ai,bi,ci,dia_i, b_i, c_i, d_i 都是可以事先 O(1)\mathcal{O}(1) 求出来的。

∏i=1n(ai(−1)∣k′∩ci∣+bi(−1)∣k′∩di∣)=∏i=1n[xk′]FWT⁡(aixci+bixdi)=[xk′]FWT⁡(∏i=1n(aixci+bixdi))=[xk′]FWT⁡(∏i=1nxci(ai+bixci⊕di))=[xk′]FWT⁡(∏i=1n(0+1xci)(ai+bixci⊕di))\begin{aligned} &\prod_{i = 1}^n (a_i(-1)^{|k' \cap c_i|} + b_i(-1)^{|k' \cap d_i|})\\ =&\prod_{i = 1}^n [x^{k'}] \operatorname{FWT}(a_ix^{c_i} + b_ix^{d_i})\\ =&[x^{k'}] \operatorname{FWT}\left(\prod_{i = 1}^n (a_ix^{c_i} + b_ix^{d_i})\right)\\ =&[x^{k'}] \operatorname{FWT}\left(\prod_{i = 1}^n x^{c_i}(a_i + b_ix^{c_i \oplus d_i})\right)\\ =&[x^{k'}] \operatorname{FWT}\left(\prod_{i = 1}^n (0 + 1x^{c_i})(a_i + b_ix^{c_i \oplus d_i})\right)\\ \end{aligned}

可以发现，这样转化过后就得到了一个第一题中的一般形式，只需要记得做完一遍后将次数从 kk 还原回 kk 即可。于是我们对每个 pp 分别做一遍就好了。那么总时间复杂度为 O(∑p=1m(n+(m−p)2m−p))=O(m(n+2m))\mathcal{O}(\sum_{p = 1}^m (n + (m - p)2^{m - p})) = \mathcal{O}(m(n + 2^m))。