问题
给定若干个数 \(a_1 \dots a_n\)，\(q\) 次询问，或单点修改，或询问第 \(i\) 个数取 \([0,a_i]\) 中任意数时，\(n\) 个数异或和是 \(z\) 的方案数。
本题的正确做法应该是贪心，但是我的贪心能力为 \(0\)，就十分诡异地发现这个东西可以推式子推出来。
一些记号：
- \(\text{popc}(i)\) 是 \(i\) 的 \(1\) 个数。
- \(\text{lb}(i)\) 是 \(i\) 的最低二进制位，如 \(\text{lb}(4) = 4,\text{lb}(7) = 1\)。
- \(V\) 是值域，这里是 \(2^{60}\)。
多个数的异或和，其实就是所有 \(\sum\limits_{j=0}^{a_i} x^j\) 做异或卷积。根据传统 FWT 的定义可以直接写出答案的式子就是：
\[\dfrac{1}{2^{\log{V}}}\sum\limits_{i=0}^{V-1} (-1)^{\text{popc}(z\&i)} \prod\limits_{j=0}^{n}\sum_{k=0}^{a_j}(-1)^{\text{popc}(k\&j)}
\]
这个式子看似难以处理，我们先看看后面一部分。
先解决一个特例：
\[\begin{align*}
\sum\limits_{i=0}^{2^k} (-1)^{\text{popc}(x\&i)} & = 2^{k-\text{popc}(x)}\sum\limits_{i=0}^{\text{popc}(x)} \dbinom{\text{popc}(x)}{i}(-1)^i \\
& = 2^{k-\text{popc}(x)}[\text{popc(x)} = 0] \\
& = 2^k[x=0]
\end{align*}
\]
我们又知道如果 \(a\) 可以拆成 \(\sum\limits_{i=1}^{n} 2^{c_i} (c_1 > c_2 > \cdots > c_n)\)，那么 \([0,a]\) 就是 \([0,2^{c_1}-1] \cup [2^{c_1},2^{c_1} + 2^{c_2} - 1] \dots\) 这样一些二的次幂构成的区间，其中前面几位是确定的，后几位是自由的。根据上面的推导，只有自由部分和 \(x\) 无交集（自由部分低于 \(\text{lb}(x)\)）时，才有贡献且一个数的贡献就是 \(1\)。经过精细推导后有如下式子：
下面记 \(C(n,x) = (n\&(x - 1)- n\&{x} + 1)\)。
\[\sum_{i=0}^{n}(-1)^{\text{popc}(x\&i)} = (-1)^{\text{popc}(x\&n)}C(n,\text{lb}(x))
\]
应用开发(4)—ArkTs开发语言 – 每天进步一点点)
)
)
