2021多校第二场之B题

B - Cannon

题意： 有一个 $2 * 10^{100}$ 的棋盘，第一行摆了 $n$ 个炮，第二行摆了 $m$ 个炮。一个炮吃掉另一个炮中间当且仅当只有一个炮。设 $f_k$ 为 $k$ 个炮吃炮事件的方案数，在两种情况下，第一种是两行可以交替发生事件；第二种是必须第一行发生完才能发生第二行，求方案数的异或和。

题解：

在有 $n$ 个炮的一行中吃一次的方案数为 $2(n-2)$
在有 $n$ 个炮的一行中吃 $m$ 次的方案数为 $2^m * (n - 2) * (n - 2 - 1) * \dots * (n - 2 - m - 1)$ ，可化简为 $2^m\frac{(n-2)!}{(n-2-m)!}$
第一行有 $n$ 个炮，第二行有 $m$ 个炮，设 $n = n - 2$ , $m = m - 2$ ，没什么实际意义，就是方便计算。

第一种情况的方案数为 $\sum_{k = 0}^{n + m}2^k\sum_{i=0}^{k}C_{k}^{i}\frac{n!}{(n-i)!}\frac{m!}{(m-(k-i))!}$
意义为，枚举每个k，对于当前k次来说，第一行发生i次，第二行发生k-i次，然后第一种情况两行可以交替进行，k个位置选i个给第一行，剩下第二行就固定了。
主要分析 $\sum_{i=0}^{k}C_{k}^{i}\frac{n!}{(n-i)!}\frac{m!}{(m-(k-i))!}$
将 $C_k^i$ 拆开 $\sum_{i=0}^{k}\frac{k!}{i!(k-i)!}\frac{n!}{(n-i)!}\frac{m!}{(m-(k-i))!}$
我们写成这样 $\sum_{i=0}^{k}k!\frac{n!}{i!(n-i)!}\frac{m!}{(k-i)!(m-(k-i))!}$
然后就可以化简为 $k!\sum_{i=0}^{k}C_n^iC_m^{k-i}$
通过 $C$ 的实际意义可以化简为 $k!C_{n+m}^k$
所以第一种情况的方案数为 $\sum_{k = 0}^{n + m}2^kk!C_{n+m}^k$

然后考虑第二种情况的方案数 $\sum_{k = 0}^{n + m}2^k\sum_{i=0}^{k}\frac{n!}{(n-i)!}\frac{m!}{(m-(k-i))!}$
这一步应该不难理解，同样地，我们主要分析 $\sum_{i=0}^{k}\frac{n!}{(n-i)!}\frac{m!}{(m-(k-i))!}$
分子分母同时乘 $(n + m - k)!$ $\sum_{i=0}^{k}\frac{n!m!}{(n + m - k)!}\frac{(n + m - k)!}{(n-i)!(m-(k-i))!}$
化简为 $\frac{n!m!}{(n + m - k)!}\sum_{i=0}^{k}C_{n + m - k}^{n - i}$
我们可以不用关心求和符号前面的式子了，将 $\sum_{i=0}^{k}C_{n + m - k}^{n - i}$ 转化为 $\sum_{i=n-k}^{n}C_{n+m-k}^i$
这一步应该不难理解，因为 $n-i$ 是单调的。
然后就是组合数的前缀和问题
我们设 $S(n,m) = \sum_{i=0}^{m}C_n^i$
就可以得到下面这些式子，用这些式子可以快速求前缀和 $S(n,m + 1) = S(n,m) + C(n,m+1)$
$S(n,m-1)=S(n,m)-C(n,m)$ $S(n+1,m)=2S(n,m)-C(n,m)$
然后我们将之前的式子改写为 $\sum_{i=0}^{n}C_{n+m-k}^i - \sum_{i=0}^{n-k-1}C_{n+m+k}^{i}$
这一步可能写得有点麻烦，看不懂聚聚们的做法。
然后对于这两个前缀和分别去求解存到两个数组里，作差就是答案，数组记为 $s$ 。
所以第二种情况的方案数就为 $\sum_{k=0}^{n+m}2^k\frac{n!m!}{(n+m-k)!}s_k$

一些细节：

不能一股脑全开 $long long$ ，内存会超
然后对于快速幂什么的，预处理一下，时间复杂度只能接受 $O(n + m)$ ，在多带个 $log$ 就会超时
最后异或的答案不要取余

#include<bits/stdc++.h>
using namespace std;

#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {   cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...);}

#define ll long long
#define ull unsigned long long
#define LL __int128
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define PII pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define PAUSE system("pause");
const double Pi = acos(-1.0);
const double eps = 1e-8;
const int maxn = 1e7 + 10;
const int maxm = 6e2 + 10;
const int mod = 1e9 + 9;
const int P = 131;
const int S = 5;

inline ll rd() {
    ll f = 0; ll x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}
void out(ll a) {if(a<0)putchar('-'),a=-a;if(a>=10)out(a/10);putchar(a%10+'0');}
#define pt(x) out(x),puts("")
inline void swap(ll &a, ll &b){ll t = a; a = b; b = t;}
inline void swap(int &a, int &b){int t = a; a = b; b = t;}
inline ll min(ll a, ll b){return a < b ? a : b;}
inline ll max(ll a, ll b){return a > b ? a : b;}

int n, m, s[maxn], s1[maxn], s2[maxn];
int f1[maxn], f2[maxn], qpow2[maxn], inv[maxn];

ll qpow(ll n, ll k, ll mod) {
    ll ans = 1;
    while(k) {
        if(k & 1)
            ans = ans * n % mod;
        n = n * n % mod;
        k >>= 1;
    }
    return ans;
}

void init(){
    s[0] = 1;
    s[1] = 1;
    qpow2[0] = 1;
    qpow2[1] = 2;
    inv[0] = 1;
    inv[1] = 1;
    for(int i = 2; i <= maxn - 5; ++i) {
        inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;
    }  
    for(ll i = 2; i <= maxn - 5; i++){
        s[i] = (ll)s[i - 1] * i % mod;
        qpow2[i] = (ll)qpow2[i - 1] * 2ll % mod;
        inv[i] = (ll)inv[i - 1] * (ll)inv[i] % mod;
    }
}

ll c(ll n, ll m){
    if(n < m) return 0;
    return (ll)s[n] * (ll)inv[m] % mod * (ll)inv[n - m] % mod;
}

void solve(){
    n = rd(), m = rd();
    n -= 2, m -= 2;
    s1[n + m] = 1;
    for(int i = n + m; i >= 1; i--) {
        s1[i - 1] = ((2ll * s1[i] % mod - 1ll * c(n + m - i, n) % mod + mod)) % mod;
    }
    s2[n - 1] = 1;
    for(int i = n - 1; i >= 1; i--) {
        s2[i - 1] = ((s2[i] % mod + 1ll * c(n + m - i, n - i) % mod + mod)) % mod;
        s2[i - 1] = ((2ll * s2[i - 1] % mod - 1ll * c(n + m - i, n - i) % mod + mod)) % mod;
    }
    for(int i = n + m; i >= 0; i--) {
        s1[i] = (s1[i] - s2[i] + mod) % mod;
    }
    ll ans1 = 0, ans2 = 0;
    // for(int i = 0; i <= n + m; i++)
    //     dbg(s[i], qpow2[i], inv[i]);
    for(int i = 0; i <= n + m; i++) {
        f1[i] = (ll)qpow2[i] * s[n + m] % mod * inv[n + m - i] % mod;
        f2[i] = (ll)qpow2[i] * s[n] % mod * s[m] % mod * inv[n + m - i] % mod * s1[i] % mod;
        // dbg(f1[i], qpow(2ll, i, mod), s[n + m], qpow(s[n + m - i], mod - 2, mod), n + m);
    }
    for(int i = 0; i <= n + m; i++) {
        ans1 ^= f1[i];
        ans2 ^= f2[i];
    }
    printf("%lld %lld\n", ans1, ans2);
}

int main() {
//    freopen("in.txt","r",stdin);
//    freopen("out.txt", "w", stdout);
    int t = 1;
    // t = rd();
    // scanf("%d", &t);
    // cin >> t;
    init();
    while(t--)
        solve();
    return 0;
}