Koxia and Sequence

题面

给定非负整数 $n,x,y$ ，对于所有满足 $\sum_{i=1}^n a_i=x,\text{OR}_{i=1}^n a_i=y$ ，的序列 $\{a_n\}$ 。求 $\bigoplus_{i=1}^n a_i$ 的异或和。

$1 \leq n < 2^{40} , 0 \leq x < 2^{60} , 0 \leq y < 2^{20}$ .

题解

牛逼题。

这异或和啥的肯定考虑位。但除了这个就不会了。

于是要死命找性质。发现 $a_i$ 内有对称性，所以 $2~|~n$ 答案为 0；并且只用考虑 $a_1$ 的情况（ $[2,n]$ 对称抵消）。

但还是不太好做，考虑两个方向：

1. 先考虑拆位， $y$ 限制好做， $x$ 限制难；
2. 先考虑 $\sum a_i=x$ ，不容易满足 $y$ 限制。

省流：考虑 2.

考虑到异或和恰好等于 $y$ 太难，我们撬开一个口子，弱化这个限制而夹缝生存——异或和是其子集。这样可以子集反演容斥得 $\sum_{z\subseteq y}(-1)^{y-z}f(z)\equiv\bigoplus_{z\subseteq y}f(z)$ 。

妈的，大的要来了。

$$\begin{aligned} f(z) &=\sum_{a_1+\cdots+a_n=x} \binom {z-2^k}{a_1-2^k}\prod_{i=2}^n\binom z{a_2}\bmod 2\\ &=\binom{nz-2^k}{x-2^k}\bmod 2\\ &=[x-2^k\subseteq nz-2^k] \end{aligned} $$

用到范德蒙德卷积并组合数，exLucas 推论 $[m\subseteq n]=\binom nm\bmod 2$ 。

代码

const int N = 0;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	ll n, x, y, ans;
	int main () {
		n = Read(), x = Read(), y = Read();
		if (!(n & 1)) { puts("0"); return 0;}
		for (ll k = 1; k <= y; k <<= 1) if (k & y)
			for (ll z = 1; z <= y; ++z) if ((z & k) && ((z | y) == y)) {
				ll u = n * z - k, v = x - k;
				ans ^= k * (u >= 0 && v >= 0 && ((u | v) == u));
			}
		printf ("%lld\n", ans);
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}