D – Xor Sum 5 (atcoder.jp)

题意：你有 $n$ 个数 $a_i$，现在每次从这 $n$ 个数中随机挑一个，重复 $k$ 次，总共会有 $n^k$ 种方案。现在对每个方案都求出其中的数的和，然后要求出所有这些和的异或和。

$n \le 10^3, k \le 10^12, a_i \le 10^3$

咋一看非常怪浪，要对一堆数的和求异或和，但是按位考虑的话又没有什么性质。

众所周知两个一样的数异或会被消掉，所以思考一下什么样的方案才会有贡献。

对于一个相同的可重集，显然它的所有可重排列的和都是相同的。假设每个元素被选中的次数是 $c_i$，那么可重排列的方案数就是

$$ \begin{aligned} \prod \binom {\sum_{j \le i} c_j} {c_i} \end_{aligned} $$

方案数是奇数的时候才会有贡献，也就是说每个组合数都必须是奇数。

然后会发现组合数的奇偶性有一个经典结论：如果 $\binom{n}{k}$ 是奇数，那么二进制表示中 $n$ 一定是 $k$ 的超集。（可以从 Lucas 定理解释。）

再思考一下换成多重排列的话这些组合数的连乘，可以想到如果每个都是奇数，那么所有 $c_i$ 的二进制表示一定就是把 $k$ 的二进制位进行了一个划分。

所以现在问题就转化成了这个：在 $k$ 的二进制表示中，$0$ 不需要操作，而每个 $1$ 都需要选择一个数填上。填上的数按照 $1$ 的位置加起来得到一个和，那么这样得到的方案一定就包含了原题中要求的所有有贡献的方案。

考虑到 $a_i \le 10^3 < 2^10$，所以可以考虑直接从低位到高位 DP 来解决这个事情。$dp_{i, j}$ 表示已经填完了 $i-1$ 以及更低的位，且当前的余数是 $j$ （$j$ 的最低位对应最终方案中的第 $i$ 位）。

有了思路，转移也就很简单了：如果 $k$ 的第 $i$ 位是 $1$，那么就枚举这这一位填上哪个 $a_i$，更新余数，然后让新的 DP 状态异或上现在的值。

这里有一个小问题，如果余数的最低位是 $1$，那么新的 DP 值应该异或上 $1 << i$；但是有些方案其实包含了偶数个不同的方案，虽然这些方案异或和不是 $0$，但是这个最低位 $1$ 的贡献肯定是不应该算的。解决方法是开一个 $mark$ 数组标记这个状态包含的方案数是奇数还是偶数，转移的时候一起更新就行了。

（方便起见代码用的刷表法。另外代码里的 $vis$ 是没必要的，因为访问不到的状态 $mark$ 肯定是 $0$，所以只需要维护 $mark$ 就行了。）

#include <bits/stdc++.h>
 
using namespace std;
 
unsigned long long dp[2][(1 << 10) + 1];
bool vis[2][(1 << 10) + 1], mark[2][(1 << 10) + 1];
 
int a[1005];
 
int main() {
 
	int n;
	long long k;
	cin >> n >> k;
 
	for (int i = 0; i < n; i++)
		cin >> a[i];
	
	vis[0][0] = true;
	mark[0][0] = true;
	int cur = 0;
 
	unsigned long long ans = 0;
 
	for (int i = 0; i < 51; i++) {
		memset(dp[cur ^ 1], 0, sizeof(dp[cur ^ 1]));
		memset(vis[cur ^ 1], 0, sizeof(vis[cur ^ 1]));
		memset(mark[cur ^ 1], 0, sizeof(mark[cur ^ 1]));
		
		for (int j = 0; j < (1 << 10); j++) {
			assert(!(dp[cur][j] >> i & 1));
 
			if (vis[cur][j]) {
				if (k >> i & 1) {
					for (int p = 0; p < n; p++) {
						int t = j + a[p];
 
						vis[cur ^ 1][t >> 1] |= true;
						mark[cur ^ 1][t >> 1] ^= mark[cur][j];
						dp[cur ^ 1][t >> 1] ^= dp[cur][j];
						
						if (mark[cur][j])
							dp[cur ^ 1][t >> 1] ^= (t & 1ll) << i;
					}
				}
			
				else {
					vis[cur ^ 1][j >> 1] |= true;
					mark[cur ^ 1][j >> 1] ^= mark[cur][j];
					dp[cur ^ 1][j >> 1] ^= dp[cur][j];
 
					if (mark[cur][j])
						dp[cur ^ 1][j >> 1] ^= (j & 1ll) << i;
				}
			}
		}
 
		cur ^= 1;
	}
 
	cout << dp[cur][0] << endl;
 
	return 0;
}