题解 | _牛客博客

Cannon

有一个 $2×10^{100}$ 的棋盘，第一行摆了 $a$ 个炮，第二行摆了 $b$ 个炮。

依次求发生 $0, 1, 2, \dots, a + b - 2$ 个炮吃炮事件的方案数。

有考虑两行之间的顺序和不考虑两行之间的顺序两个子问题。

$1 \leq a, b \leq 5 \times 10^6$

一行 $n$ 个炮操作 $m$ 次的方案是 $2^m \dfrac{(n - 2)!}{(n - 2 - m)!}$ 。

设 $n = a - 2, m = b - 2$ ，问题即求
$ $\begin{aligned} ans_1 &= 2^k \sum_{i = 0}^k \binom{k}{i}\frac{n!}{(n - i)!}\frac{m!}{(m - k + i)!}\\ &= 2^k k!\sum_{i = 0}^k \frac{n!}{(n - i)!i!}\frac{m!}{(m - k + i)!(k-i)!}\\ &= 2^k k!\sum_{i = 0}^k \binom{n}{i}\binom{m}{k-i}\\ &= 2^k k!\binom{n+m}{k}\\ ans_2 &= 2^k \sum_{i = 0}^k \frac{n!}{(n - i)!}\frac{m!}{(m - k + i)!}\\ &= 2^k \frac{n!m!}{(n + m - k)!}\sum_{i = 0}^k \frac{(n+m-k)!}{(n-i)!(m-k+i)!}\\ &= 2^k \frac{n!m!}{(n + m - k)!}\sum_{i = 0}^k \binom{n+m-k}{n-i}\\ &= 2^k \frac{n!m!}{(n + m - k)!}\sum_{i = n}^{n-k} \binom{n+m-k}{i} \end{aligned}$ $

问题一直接递推，问题二维护一个组合数前缀和即可。

// Author:  HolyK
// Created: Tue Jul 20 21:51:46 2021
#include <bits/stdc++.h>
#define dbg(a...) fprintf(stderr, a)
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;
constexpr int P(1e9 + 9);
inline void inc(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}
int fpow(int x, int k = P - 2) {
  int r = 1;
  for (; k; k >>= 1, x = 1LL * x * x % P) {
    if (k & 1) r = 1LL * r * x % P;
  }
  return r;
}
constexpr int N(1e7 + 5);
int n, m, fac[N], ifac[N];
int bin(int n, int m) {
  return m >= 0 && m <= n ? 1LL * fac[n] * ifac[m] % P * ifac[n - m] % P : 0;
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n >> m;
  n -= 2, m -= 2;
  fac[0] = ifac[0] = 1;
  int k = n + m;
  for (int i = 1; i <= k; i++) fac[i] = 1LL * fac[i - 1] * i % P;
  ifac[k] = fpow(fac[k]);
  for (int i = k - 1; i; i--) ifac[i] = 1LL * ifac[i + 1] * (i + 1) % P;
  int ans = 1;
  for (int i = 1, x = 1; i <= k; i++) {
    x = 2LL * x * (k - i + 1) % P;
    ans ^= x;
  }
  std::cout << ans << " ";
  ans = 1;
  int s1 = 0, s2;
  for (int i = 0; i < n; i++) inc(s1, bin(k, i));
  inc(s2 = s1, bin(k, n));
  for (int i = 1, x = fpow(bin(k, n)); i <= k; i++) {
    s1 = (s1 - bin(k - i, n - i) + P) * (P + 1LL >> 1) % P;
    s2 = (s2 + bin(k - i, n)) * (P + 1LL >> 1) % P;
    x = 2LL * x * (k - i + 1) % P;
    ans ^= 1LL * x * (s2 - s1 + P) % P;
  }
  std::cout << ans << "\n";
  return 0;
}