CodeforcesGoodBye2022CF1770FKoxiaandSequence题解

题目链接

注意题目要求的是所有好序列的所有元素的XOR之和的XOR之和。我一开始以为是所有XOR之和的加法和导致不知道官方题解在讲什么。

假设我们枚举一个位置\(1\le i\le n\)和一个数值\(v\)，统计第i个位置为v的好序列的个数，如果个数为奇数就可以把最终答案异或上v。由于对于同一个v和不同的i，这个个数都相同，所以n为偶数的时候最终答案是0。要先把这个特判掉，不然影响后面思考。n为奇数的情况，其实我们就只要枚举所有v，求出\(a_1=v\)的好序列的个数，如果是奇数就把答案异或上v就行了。把数值的每一位拆开进一步转化成这样：枚举一个bit i(\(0\le i\le19\))，求出\(a_1\)的二进制第i位为1的好序列的个数，如果个数是奇数则最终答案的第i位为1。观察可以发现这个问题形式与之前的那个等价。

我们先枚举i。一个好的序列要满足所有元素的或=y，要求刚好=y是很难计算的，不如用容斥：定义\(f_s\)表示所有元素的或是s的子集(可以=s)，且和为x，同时满足\(a_1\)的第i位为1的好序列个数。那么或刚好=y的好序列数量=\(\sum_{s\subseteq y}f_s(-1)^{|s\ xor\ y|}\)。令\(g_s=f_s\ mod \ 2\)，那么或刚好=y的好序列数量奇偶性=\(\bigoplus_{s\subseteq y}g_s\)，其中\(\bigoplus\)表示异或和。

当确定了i和s时，\(g_s\)其实是好算的。先看不要求\(a_1\)的第i位为1的情况，\(g_s=(\sum_{t_1,t_2\cdots t_n,\sum_t=x} \prod_{i=1}^n [t_i\&s=t_i])mod\ 2\)。有一个关于组合数的结论，\([m\&n=m]=\binom nm \ mod\ 2\)，也就是\(\binom nm\)为奇数的充要条件是\(m\)为\(n\)的子集。所以\(g_s=(\sum_{t_1,t_2\cdots t_n,\sum_t=x} \prod_{i=1}^n \binom{s}{t_i}\ mod\ 2)mod\ 2=\binom{ns}{x}\ mod\ 2\)。加上要求\(a_1\)的第i位为1的条件，其实也只要改成要求\(s\)的第i位为1，然后\(g_s=\binom{ns-2^i}{x-2^i}\ mod\ 2\)就行了。

枚举所有i和s然后算出所有\(g_s\)就能求出最终答案了。总时间复杂度\(O(ylogy)\)。