CF2034F2 Khayyam's Royal Decree (Hard Version)

把问题改写成在网格图上走，一个红球或蓝球对应了网格图上的一条边。最后只要把答案除以 \(\dbinom{n+m}{m}\) 即可。

价值 \(\times 2\) 不好表示，考虑把带 \(2^c\) 倍价值的球看成一个球 和 \(2^c-1\) 个“复制品”。每次使用道具相当于将每个球都复制一遍。

考虑对于每个道具，计算其从非“复制品”复制出来的球的贡献。

对于一条 \((0,0)\to (n,m)\) 的路径，其中一个点 \((x,y)\) 的贡献 \(2^c\)，\(c\) 为之后的道具数量。此处道具的限制为【当前背包里有 \(r\) 个红球，\(b\) 个蓝球】。

考虑 \(2^c\) 的组合意义，其可以表示为钦定一个道具的子集必须经过。

于是可以 dp，\(f_i\) 为从道具 \(i\) 对应的点开始走，并钦定若干道具必须经过的方案数。

显然有 \(f_i=\sum f_j\times tot_{i,j}\)，其中 \(tot_{i,j}\) 为从道具 \(i\) 到道具 \(j\) 的方案数，即 \(\dbinom{r_j-r_i+b_j-b_i}{r_j-r_i}\)。

考虑怎么计算答案。方便起见，添加两个道具 \((0,0)\) 和 \((n,m)\)。其编号为 \(0\) 和 \(k+1\)。那么对于一个道具 \(i\)，其贡献为 \(tot_{0,i}\times(2\times r_i+b_i)\times f_i\)，求和即可。

#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
using namespace std;
void file() {
  freopen("1.in", "r", stdin);
  freopen("1.out", "w", stdout);
}
using ll = long long;

namespace QwQ {
  const int kMod = 998244353;
  void Add(int& x, int y) { ((x += y) >= kMod) && (x -= kMod); }
  void Sub(int& x, int y) { ((x -= y) < 0) && (x += kMod); }
  int Sum(int x, int y) { return Add(x, y), x; }
  int Dif(int x, int y) { return Sub(x, y), x; }
  int qpow(int x, int y) {
    int b = x, r = 1;
    for(; y; b = (ll)b * b % kMod, y /= 2) {
      if(y & 1) {
        r = (ll)r * b % kMod;
      }
    }
    return r;
  }

  const int kN = 4e5 + 5, kL = 5005;
  int n, m, k;
  array<int, kN> mul, imul;
  array<array<int, kL>, kL> tot;
  array<int, kL> f;

  struct Scr {
    int r, b;
    Scr() {  }
    Scr(int _r, int _b) {
      r = _r, b = _b;
    }
    int Eval() { return 2 * r + b; }
  };
  array<Scr, kL> scr;

  void init() {
    mul[0] = 1;
    for(int i = 1; i < kN; i++) {
      mul[i] = (ll)mul[i - 1] * i % kMod;
    }
    imul[kN - 1] = qpow(mul[kN - 1], kMod - 2);
    for(int i = kN - 2; i >= 0; i--) {
      imul[i] = (ll)imul[i + 1] * (i + 1) % kMod;
    }
  }
  int C(int n, int m) {
    if(min({n, m, n - m}) < 0) {
      return 0;
    }else {
      return (ll)mul[n] * imul[m] % kMod * imul[n - m] % kMod;
    }
  }
  int invC(int n, int m) {
    if(min({n, m, n - m}) < 0) {
      return 0;
    }else {
      return (ll)imul[n] * mul[m] % kMod * mul[n - m] % kMod;
    }
  }

  void solve() {
    cin >> n >> m >> k;
    for(int i = 1; i <= k; i++) {
      cin >> scr[i].r >> scr[i].b;
      scr[i].r = n - scr[i].r;
      scr[i].b = m - scr[i].b;
    }
    scr[++k] = Scr(0, 0);
    scr[++k] = Scr(n, m);
    sort(scr.data() + 1, scr.data() + k + 1,
      [&](Scr x, Scr y) { return x.r + x.b < y.r + y.b; });
    fill_n(f.data(), k + 1, 0);
    f[k] = 1;
    for(int i = k; i >= 1; i--) {
      tot[i][i] = 1;
      int r = scr[i].r, b = scr[i].b;
      for(int j = i + 1; j <= k; j++) {
        int R = scr[j].r, B = scr[j].b;
        if((R >= r) && (B >= b)) {
          tot[i][j] = C(R - r + B - b, R - r);
          Add(f[i], (ll)tot[i][j] * f[j] % kMod);
        }
      }
    }
    int ans = 0;
    for(int i = 1; i <= k; i++) {
      Add(ans, (ll)tot[1][i] * f[i] % kMod * scr[i].Eval() % kMod);
    }
    cout << (ll)ans * invC(n + m, n) % kMod << "\n";
  }

  int main() {
    file();
    ios::sync_with_stdio(0), cin.tie(0);
    init();
    int T = 1;
    cin >> T;
    while(T--) solve();
    return 0;
  }
} // QwQ

int main() {
  return QwQ::main();
}