CF1942G Bessie and Cards

· · 题解

CF1942G Bessie and Cards

先判断一组方案是否成功。设还能抓的牌的数量为 y，初始为 5。每抓到一张 Draw 0 或特殊牌则 y 减去 1，每抓到一张 Draw 2 则 y 加上 1，抓到 Draw 1 没有任何影响。当 y = 0 且没有抓到所有特殊牌时失败。将 Draw 1 删去不影响一组方案是否合法。考虑到最终答案要求概率而非方案数，于是令 b = 0，答案不变。

注意到失败的方案一定有 y = 0，于是我们枚举 y 变为 0 的时刻，将特殊牌视为 Draw 0，算失败的方案数。

经典格路计数。枚举在第 x 次抓牌时 y 第一次变成 0，则 x \geq 5 且 x - 5 是偶数。考虑 (x, y) 形成的相图，计算从 (0, 5) 走到 (x, 0)，每一步只能向右上或者右下走，且之前没有碰到过 x 轴的方案数。等价于从 (0, 5) 走到 (x - 1, 1) 且之前没有碰到过 x 轴的方案数。反射容斥，等价于从 (0, 5) 走到 (x - 1, 1) 的方案数减去走到 (x - 1, -1) 的方案数。

设 c' = \frac {x - 5} 2 表示抓了多少张 Draw 2，a' = x - c' 表示抓了多少张 Draw 0，则方案数为 \binom {i - 1} {a' - 1} - \binom {i - 1} {a'}。乘以任意安排 y = 0 之后的贡献系数 \binom {n - i} {a + 5 - a'}，其中 n 表示总牌数。再乘以从 a + 5 张牌中选 5 张特殊牌的方案数，不能全选 y = 0 之前，即 \binom {a + 5} 5 - \binom {a'} 5。

时间复杂度 \mathcal{O}(\min(a, c))。

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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdi = pair<double, int>;
using pdd = pair<double, double>;
using ull = unsigned long long;

#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)

bool Mbe;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
//mt19937_64 rnd(1064);
int rd(int l, int r) {
  return rnd() % (r - l + 1) + l;
}

constexpr int mod = 998244353;
void addt(int &x, int y) {
  x += y, x >= mod && (x -= mod);
}
int add(int x, int y) {
  return x += y, x >= mod && (x -= mod), x;
}
int ksm(int a, ll b) {
  int s = 1;
  while(b) {
    if(b & 1) s = 1ll * s * a % mod;
    a = 1ll * a * a % mod, b >>= 1;
  }
  return s;
}

constexpr int Z = 1e6 + 5;
int fc[Z], ifc[Z], inv[Z];
int bin(int n, int m) {
  if(n < m) return 0;
  return 1ll * fc[n] * ifc[m] % mod * ifc[n - m] % mod;
}
void init_fac(int Z) {
  for(int i = fc[0] = 1; i < Z; i++) fc[i] = 1ll * fc[i - 1] * i % mod;
  ifc[Z - 1] = ksm(fc[Z - 1], mod - 2);
  for(int i = Z - 2; ~i; i--) ifc[i] = 1ll * ifc[i + 1] * (i + 1) % mod;
  for(int i = 1; i < Z; i++) inv[i] = 1ll * fc[i - 1] * ifc[i] % mod;
}

// ---------- templates above ----------

int n, A, B, C;
void solve(int T) {
  cin >> A >> B >> C, A += 5, B = 0;
  int ans = 0, n = A + C;
  for(int i = 5; i <= n; i += 2) {
    int nc = i - 5 >> 1, na = i - nc;
    if(na > A || nc > C) continue;
    int coef = 1ll * add(bin(i - 1, na - 1), mod - (i > na ? bin(i - 1, na) : 0)) * bin(n - i, A - na) % mod;
    addt(ans, 1ll * coef * add(bin(A, 5), mod - bin(na, 5)) % mod);
  }
  cout << (1 + mod - 1ll * ans * ifc[n] % mod * fc[C] % mod * fc[A - 5] % mod * 120 % mod) % mod << "\n";
}

/*
1
2 0 1
*/ 

bool Med;
signed main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  init_fac(Z);
  int T = 1;
  cin >> T;
  while(T--) solve(T);

  fprintf(stderr, "%.3lf ms\n", 1e3 * clock() / CLOCKS_PER_SEC);
  return 0;
}

/*
g++ a.cpp -o a -std=c++14 -O2 -DALEX_WEI
*/