「解题报告」ARC124F Chance Meeting

· · 题解

？这你评 3246？好弱智。

首先容易发现，两个人的路径只会相交在一条直线上，那么若干个交点就都在这一条直线上。

考虑容斥求这个问题，拿至少出现 1 个交点的方案数减去至少出现 2 个交点的方案数就是答案。

如何统计至少出现 1 个交点的方案数？一条直线上的若干交点能够让我们联想到一条链，那么我们可以拿交点数减去相邻两个交点对数，就是有多少种方案数。

首先考虑交点数。考虑枚举交点 (x, y)，那么有：

\begin{aligned} &\sum_{x=0}^w \sum_{y=0}^h \binom{2x + h}{x, x, y, h - y} \binom{2(w - x) + h}{w - x, w - x, y, h - y}\\ =&\sum_{x=0}^w \sum_{y=0}^h \binom{2x+h}{x} \binom{x + h}{x} \binom{h}{y}\binom{2(w-x)+h}{w-x} \binom{w - x + h}{w - x} \binom{h}{y}\\ =&\sum_{x=0}^w \binom{2x+h}{x} \binom{x + h}{x}\binom{2(w-x)+h}{w-x} \binom{w - x + h}{w - x} \sum_{y=0}^h \binom{h}{y}^2\\ =&\sum_{x=0}^w \binom{2x+h}{x} \binom{x + h}{x}\binom{2(w-x)+h}{w-x} \binom{w - x + h}{w - x} \binom{2h}{h}\\ =&\binom{2h}{h}\sum_{x=0}^w \binom{2x+h}{x} \binom{x + h}{x}\binom{2(w-x)+h}{w-x} \binom{w - x + h}{w - x} \\ \end{aligned}

设 f_i = \binom{2i + h}{i} \binom{i + h}{i}，那么上式就是一个卷积的形式。我们不妨设 g_i = \sum_{j=0}^i f_j f_{i - j}，那么上式子就是 \binom{2h}{h} g_w。

然后考虑相邻交点对数。这个相当于我们枚举两个点，然后需要保证这两个点中间不会有另外一个交点。发现这其实就是一个卡特兰数，那么答案其实就是 \binom{2h}{h} \sum_{i=0}^{w - 1} g_i C_{w - 1 - i}。

那么至少有 1 个交点的方案数就统计完了。统计至少有 2 个交点的方案数也是类似的，我们拿相邻交点对数减去相邻三个交点对数就是答案。

相邻三个交点对数也是同样的，我们选取两个点，要求这中间恰好有一个交点，这个方案数就是卡特兰数卷积一下，也很容易算，懒得写式子了。

然后就做完了，好弱智。

void pre(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = 1ll * fac[i - 1] * i % P;
    inv[n] = qpow(fac[n], P - 2);
    for (int i = n; i >= 1; i--)
        inv[i - 1] = 1ll * inv[i] * i % P;
}
Polynomial f, g, c, d;
int main() {
    pre(800000);
    scanf("%d%d", &h, &w);
    h--, w--;
    f.set(w);
    for (int i = 0; i <= w; i++) {
        f[i] = 1ll * C(2 * i + h, h) * C(2 * i, i) % P;
    }
    g = f * f;
    c.set(w);
    c[0] = 1;
    for (int i = 1; i <= w; i++) {
        c[i] = (C(2 * i, i) - C(2 * i, i - 1) + P) % P;
    }
    d = c * c;
    int ans = 0;
    // at least 1: 1 - 2
    ans = g[w];
    for (int i = 0; i <= w - 1; i++) {
        ans = (ans - 2ll * g[i] * c[w - 1 - i] % P + P) % P;
    }
    // at least 2: 2 - 3
    for (int i = 0; i <= w - 1; i++) {
        ans = (ans - 2ll * g[i] * c[w - 1 - i] % P + P) % P;
    }
    for (int i = 0; i <= w - 2; i++) {
        ans = (ans + 4ll * g[i] * d[w - 2 - i] % P + P) % P;
    }
    ans = 1ll * ans * C(2 * h, h) % P;
    printf("%d\n", ans);
    return 0;
}