场上被 T6 做局了，赛后单杀了来写篇题解。

由于只关心异或和，可以将非严格递增序列看作可重集。那么我们只关心 SS 中每种元素出现次数的奇偶性。求出不可重集的方案数后每种数加入偶数个即可。我们求出 hih_i 表示大小为 ii 且异或和在 TT 中的 SS 的子集个数，答案就是这样：

∑i=0∣S∣hi((n−i)/2+∣S∣∣S∣)\sum_{i = 0}^{|S|} h_i \binom{(n - i) / 2 + |S|}{|S|}

我们规定 xaxb=xa⊕b,yayb=ya+bx^ax^b = x^{a \oplus b}, y^ay^b = y^{a+b}，那么可以写出 hh 的生成函数：

∑a∈T[xa]∏b∈S(1+xby)\sum_{a \in T} [x^a] \prod_{b \in S} (1 + x^by)

先考虑后面部分，套路地 FWT 一下变成点乘：

fk=[xk]FWT⁡(∏b∈S(1+xby))=∏b∈S[xk]FWT⁡(1+xby)=∏b∈S(1+y(−1)∣k∩b∣)\begin{aligned} f_k &= [x^k] \operatorname{FWT}\left(\prod_{b \in S} (1 + x^by)\right)\\ &= \prod_{b \in S} [x^k] \operatorname{FWT}(1 + x^by)\\ &= \prod_{b \in S} (1 + y(-1)^{|k \cap b|})\\ \end{aligned}

最后还要 IFWT 回去求出各项系数：

gk=12v[xk]FWT⁡(∑j=02v−1fjxj)=12v∑j=02v−1[xk]FWT⁡(fjxj)=12v∑j=02v−1(−1)∣k∩j∣fj=12v∑j=02v−1(−1)∣k∩j∣∏b∈S(1+y(−1)∣j∩b∣)\begin{aligned} g_k &= \frac 1{2^v} [x^k] \operatorname{FWT}\left(\sum_{j = 0}^{2^v - 1} f_jx^j\right)\\ &= \frac 1{2^v} \sum_{j = 0}^{2^v - 1} [x^k] \operatorname{FWT}(f_jx^j)\\ &= \frac 1{2^v} \sum_{j = 0}^{2^v - 1} (-1)^{|k \cap j|}f_j\\ &= \frac 1{2^v} \sum_{j = 0}^{2^v - 1} (-1)^{|k \cap j|} \prod_{b \in S} (1 + y(-1)^{|j \cap b|})\\ \end{aligned}\\

那么我们要求的东西变成了这样：

12v∑a∈T∑j=02v−1(−1)∣a∩j∣∏b∈S(1+y(−1)∣j∩b∣)\frac 1{2^v} \sum_{a \in T} \sum_{j = 0}^{2^v - 1} (-1)^{|a \cap j|} \prod_{b \in S} (1 + y(-1)^{|j \cap b|})\\

调换一下求和顺序：

12v∑j=02v−1∑a∈T(−1)∣a∩j∣∏b∈S(1+y(−1)∣j∩b∣)\frac 1{2^v} \sum_{j = 0}^{2^v - 1} \sum_{a \in T} (-1)^{|a \cap j|} \prod_{b \in S} (1 + y(-1)^{|j \cap b|})\\

注意到后面的乘积里面只有 (1−y)(1 - y) 和 (1+y)(1 + y)：

caj=∑a∈T[∣a∩j∣ mod 2=1]cbj=∑b∈S[∣b∩j∣ mod 2=1]12v∑j=02v−1(∣T∣−2caj)(1+y)∣S∣−cbj(1−y)cbjca_j = \sum_{a \in T} [|a \cap j| \bmod 2 = 1]\\ cb_j = \sum_{b \in S} [|b \cap j| \bmod 2 = 1]\\ \frac 1{2^v} \sum_{j = 0}^{2^v - 1} (|T| - 2ca_j) (1 + y)^{|S| - cb_j} (1 - y)^{cb_j}\\

再次合并同类项：

∑i=0∣S∣coi(1+y)i(1−y)∣S∣−i\sum_{i = 0}^{|S|} co_i (1 + y)^i (1 - y)^{|S| - i}\\

那么直接 O(∣S∣2)\mathcal O(|S|^2) 求即可。还有一个问题是 cajca_j 怎么快速算：考虑把所有的 ∣a∩j∣ mod 2|a \cap j| \bmod 2 压到 bitset 里，然后每次 j←j+1j \gets j + 1 的时候相当于是反转了 jj 的二进制表示的一段后缀，我们预处理出每种长度的后缀对 bitset 造成的影响，每次异或一下再调用 count() 即可做到 O(2v∣T∣ω)\mathcal O\left(\frac{2^v|T|}\omega\right) 求出所有 cajca_j，cbjcb_j 同理。

那么总时间复杂度就是 O(∣S∣2+2v(∣S∣+∣T∣)ω+q∣S∣)\mathcal O\left(|S|^2 + \frac{2^v(|S| + |T|)}\omega + q|S|\right)，其中 v=28v = 28，可以通过。

代码中偷懒直接写了 O(n)O(n) 预处理组合数，要规避掉也是简单的，一开始那个形式显然是一个只和 nn 有关的 ∣S∣+1|S| + 1 次多项式，O(∣S∣2)\mathcal O(|S|^2) 插值求出各项系数后也可以单次 O(∣S∣)\mathcal O(|S|) 查询答案。好像比 std 还优一点。