2021牛客暑期多校2 B

题目大意

有一个棋盘只有两行，但有 $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;
}