题解：CF2034F2 Khayyam's Royal Decree (Hard Version)

· · 题解

首先对题意做如下转化：

将 ruby 记作 A，sapphire 记作 B，于是整个过程可以记作由 n 个 A 和 m 个 B 构成的序列；并且通过观察到这样的序列中以 A 开头和以 B 开头的序列数量之比恰好为 n:m，可以归纳得到所有合法的表示序列所代表的过程的概率相等。

转化题意为在网格图上有 k 个关键点，横向边权值为 1，纵向边权值为 2；一条合法路径从 (0,0) 出发，每次向右或向下走直到 (n,m)，设该路径中某条边之前经过的关键点数为 c，该边的贡献为 2^c 乘边权，该路径的权值为路径上所有边贡献之和。要求所有合法路径的权值和。

考虑将 2^c 拆贡献，注意到这是该边之前经过的关键点集合的子集数量。所以我们定义一个方案为一个条路径和其上的一个关键点集合，我们使一条路径上的某条边只在所有只选了该边之前的关键点的方案中被计边权的贡献即可，于是一个方案的权值就应为路径上方案内最后一个关键点到终点上所有边的边权和（若关键点集为空则为整个路径上的边权和）。

这样我们通过自选关键点，规避掉了直接 DP 中“两个关键点间不经过其它关键点的路径条数”的问题。

#include<iostream>
#include<cstring>

const int N = 2e5, K = 5e3, P = 998244353;
int cas, n, m, k, sm, x[K], y[K], f[K], fc[N*2+1], ifc[N*2+1];
long long inline calc(int x, int y) { return 1ll*fc[x+y]*ifc[x]%P*ifc[y]%P; }
int dfs(int i) {
    if (~f[i]) return f[i];
    f[i] = calc(x[i], y[i]);
    for (int j=0; j<k; j++)
        if (x[j] <= x[i] && y[j] <= y[i] && i != j)
            f[i] = (f[i]+dfs(j)*calc(x[i]-x[j], y[i]-y[j]))%P;
    return f[i];
}
int main() {
    *fc = ifc[N*2] = 1;
    for (int i=1; i<=N*2; i++) fc[i] = 1ll*fc[i-1]*i%P;
    for (int a=fc[N*2], b=P-2; b; b>>=1, a=1ll*a*a%P)
        if (b&1) ifc[N*2] = 1ll*ifc[N*2]*a%P;
    for (int i=N*2; i; i--) ifc[i-1] = 1ll*ifc[i]*i%P;
    for (std::cin >> cas; cas--; std::cout << sm << '\n') {
        std::cin >> n >> m >> k, memset(f, -1, k*4), sm = 0;
        for (int i=0; i<k; i++) std::cin >> x[i] >> y[i];
        for (int i=0; i<k; i++) sm = (sm+dfs(i)*
            (2ll*(n-x[i])+m-y[i])%P*calc(n-x[i], m-y[i]))%P;
        sm = (1ll*sm*ifc[n+m]%P*fc[n]%P*fc[m]+2*n+m)%P;
    }
}