2021牛客暑期多校2 B.Cannon

题目大意

有一个棋盘只有两行，但有 $10^{1000}$ 列，第一行上有 $x$ 个炮，第二行上有 $y$ 个炮。

众所周知，中国象棋中炮吃一个子时需要中间有一棋子作为炮架。记发生 $k$ 次炮吃炮事件的方案数 $\pmod{10^9+9}$ 为 $f_k$，输出 $\bigoplus\limits_{k=0}^{x+y-4}f_k$。题目需要输出两个答案，分别对应两个限制条件：1.不考虑两行发生事件的顺序；2.事件必须先在第一行发生，之后再在第二行发生，不能再返回第一行发生。

思路

对于某一行上共 $r$ 个炮，考虑哪一个炮作为炮架，产生一次炮吃炮事件的方案数为 $2(r-2)$；因此，产生 $t$ 次炮吃炮事件的方案数为 $2(r-2)\times 2(r-1-2)\times\cdots\times 2(r-t+1-2)=2^t\frac{(r-2)!}{(r-2-t)!}$。

枚举 $0\le i\le k$，表示第一行发生 $i$ 次炮吃炮事件，第二行发生 $k-i$ 次炮吃炮事件。对于答案1，我们要从 $k$ 次炮吃炮中选出 $i$ 次在第一行中发生的，$f_{1,k}=\sum\limits_{i=0}^k\binom{k}{i}\times 2^i\frac{(x-2)!}{(x-2-i)!}\times 2^{k-i}\frac{(y-2)!}{[y-2-(k-i)]!}$；对于答案2，先在第一行发生 $i$ 次事件，再在第二行发生 $k-i$ 次事件，$f_{2,k}=\sum\limits_{i=0}^k2^i\frac{(x-2)!}{(x-2-i)!}\times 2^{k-i}\frac{(y-2)!}{[y-2-(k-i)]!}$。

令 $a=x-2$，$b=y-2$。

$$ \begin{aligned} f_{1,k}&=2^k\sum\limits_{i=0}^k\frac{k!}{i!(k-i)!}\frac{a!}{(a-i)!}\frac{b!}{[b-(k-i)]!}\\ &=2^kk!\sum\limits_{i=0}^k\frac{a!}{i!(a-i)!}\frac{b!}{(k-i)![b-(k-i)]!}\\ &=2^kk!\sum\limits_{i=0}^k\binom{a}{i}\times \binom{b}{k-i}\\ &a+b\ 个物品中拿\ k\ 个，就等价于枚举\ i，从\ a\ 中拿\ i\ 个，从\ b\ 中拿\ k-i\ 个。\\ &=2^kk!\binom{a+b}{k} \end{aligned} \quad \begin{aligned} f_{2,k}&=2^k\sum\limits_{i=0}^k\frac{a!}{(a-i)!}\frac{b!}{[b-(k-i)]!}\\ &=2^k\frac{a!b!}{(a+b-k)!}\sum\limits_{i=0}^k\frac{(a+b-k)!}{(a-i)![b-(k-i)!]}\\ &=2^k\frac{a!b!}{(a+b-k)!}\sum\limits_{i=0}^k\binom{a+b-k}{a-i}\\ \end{aligned} $$

枚举 $0\le k\le a+b$，预处理阶乘、阶乘的逆元、$2$ 的幂次，可在 $O(x+y)$ 的时间内得到 $f_1$。我们接下来要设法在同样的时间得到 $f_2$，令 $S_k=\sum\limits_{i=0}^k\binom{a+b-k}{a-i}$，我们可以考虑 $S_{k}$ 同 $S_{k+1}$ 的关系，使用移步法解决。

$$ \begin{aligned} S_{k+1}&=\sum\limits_{i=0}^{k+1}\binom{a+b-k-1}{a-i}\\ S_k&=\sum\limits_{i=0}^k\binom{a+b-k}{a-i}\\ &=\sum\limits_{i=0}^k\binom{a+b-k-1}{a-i}+\sum\limits_{i=0}^k\binom{a+b-k-1}{a-i-1}\\ &=\left[S_{k+1}-\binom{a+b-k-1}{a-k-1}\right]+\left[S_{k+1}-\binom{a+b-k-1}{a}\right]\\ &=2S_{k+1}-\binom{a+b-k-1}{a}-\binom{a+b-k-1}{b} \end{aligned} $$

倒序枚举 $0\le k\le a+b$，$S_{a+b}=1$，得到 $f_{2,a+b}=2^{a+b}a!b!$，即可在 $O(x+y)$ 时间内得到答案。

代码

#include<iostream>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 9;
const int MAX_SIZE = 1e7 + 4;
int fac[MAX_SIZE], inv[MAX_SIZE];
int power2[MAX_SIZE];
ll QuickPower(ll a, ll b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1)
		{
			res = res * a % MOD;
		}
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}
void Init()
{
	// 预处理阶乘
	// 预处理2的幂次
	fac[0] = power2[0] = 1;
	for (int i = 1;i < MAX_SIZE;i++)
	{
		fac[i] = 1ll * fac[i - 1] * i % MOD;
		power2[i] = 1ll * power2[i - 1] * 2 % MOD;
	}
	// 预处理阶乘的逆元
	inv[MAX_SIZE - 1] = QuickPower(fac[MAX_SIZE - 1], MOD - 2);
	for (int i = MAX_SIZE - 2;i >= 0;i--)
	{
		inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;
	}
}
inline ll C(int n, int m)
{
	return m > n ? 0 : 1ll * fac[n] * inv[n - m] % MOD * inv[m] % MOD;
}
int main()
{
	Init();
	int x, y;
	cin >> x >> y;
	int a = x - 2, b = y - 2;
	int ans1 = 0;
	for (int k = 0;k <= a + b;k++)
	{
		ans1 ^= 1ll * power2[k] * fac[k] % MOD * C(a + b, k) % MOD;
	}
	cout << ans1 << ' ';
	int ans2 = 1ll * power2[a + b] * fac[a] % MOD * fac[b] % MOD;
	// 记录S[k+1]
	int lastS = 1;
	for (int k = a + b - 1;k >= 0;k--)
	{
		int curS = 2 * lastS - C(a + b - k - 1, a) - C(a + b - k - 1, b);
		curS = (curS % MOD + MOD) % MOD;
		ans2 ^= 1ll * power2[k] * fac[a] % MOD * fac[b] % MOD * inv[a + b - k] % MOD * curS % MOD;
		lastS = curS;
	}
	cout << ans2 << endl;
	return 0;
}