2021牛客暑期多校2 B

题目大意

有一个棋盘只有两行，但有 列，第一行上有 个炮，第二行上有 个炮。

众所周知，中国象棋中炮吃一个子时需要中间有一棋子作为炮架。记发生 次炮吃炮事件的方案数 为 ，输出 。题目需要输出两个答案，分别对应两个限制条件：1.不考虑两行发生事件的顺序；2.事件必须先在第一行发生，之后再在第二行发生，不能再返回第一行发生。

思路

对于某一行上共 个炮，考虑哪一个炮作为炮架，产生一次炮吃炮事件的方案数为 ；因此，产生 次炮吃炮事件的方案数为 。

枚举 ，表示第一行发生 次炮吃炮事件，第二行发生 次炮吃炮事件。对于答案1，我们要从 次炮吃炮中选出 次在第一行中发生的，；对于答案2，先在第一行发生 次事件，再在第二行发生 次事件，。

令 ，。

枚举 ，预处理阶乘、阶乘的逆元、 的幂次，可在 的时间内得到 。我们接下来要设法在同样的时间得到 ，令 ，我们可以考虑 同 的关系，使用移步法解决。

倒序枚举 ，，得到 ，即可在 时间内得到答案。

代码

#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;
}