P5014 水の三角(修改版) 题解

Link_Cut_Y · 2023-08-27 16:37:57 · 题解

给定三角网格图，求从点 (1, 1) 走到点 (n, m) 的路径方案数。

首先将三角推平，变成这个样子：

1
|
2 - 3
|   |
4 - 5 - 6

上图是没有斜线的情况，这就是裸的卡特兰数。由于要向右走 m - 1 步，向下走 n - 1 步，所以设 n' = n - 1, m' = m - 1，答案即为：

接下来考虑走斜线的情况。假设走了 i 次斜线，那么向下走的次数变为了 n_0 = n' - i，向右走的次数变为了 m_0 = m' - i。现在分两种情况讨论：

• 只走直线。如上，方案数即为：

  \binom{n_0 + m_0}{m_0} - \binom{n_0 + m_0}{m_0 - 1}

• 走斜线。根据插板法，方案数即为：

  \binom{n_0 + m_0 + i}{i}

  根据乘法原理，直接将两种方案乘起来就可以了。故方案数为：

  \sum \limits_{i = 0}^{m'} \binom{n_0 + m_0 + i}{i} \left [ \binom{n_0 + m_0}{m_0} - \binom{n_0 + m_0}{m_0 - 1} \right ]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define int long long

using namespace std;

const int N = 2000010;
const int mod = 998244353;
int T, fac[N], ifac[N];
int power(int a, int b) {
    int ans = 1; for (; b >>= 1; a = a * a % mod)
        if (b & 1) ans = ans * a % mod; return ans;
}
void init(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i ++ )
        fac[i] = 1ll * fac[i - 1] * i % mod;
    ifac[n] = power(fac[n], mod - 2);
    for (int i = n - 1; i >= 0; i -- )
        ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
}
int C(int n, int m) {
    return fac[n] * ifac[m] % mod * ifac[n - m] % mod; 
}
int f(int n, int m) { 
    return (C(n, m) % mod - C(n, m + 1) % mod + mod) % mod; 
}
signed main() {
    scanf("%lld", &T); init(N - 10);
    while (T -- ) {
        int x; scanf("%lld", &x);
        int n = sqrt(x); 
        while (n * (n + 1) / 2 < x) n ++ ;
        int m = x - (n * (n - 1) / 2);
        int ans = 0; n -- , m -- ;
        for (int i = 0; i <= m; i ++ ) {
            int n0 = n - i, m0 = m - i;
            (ans += (C(n0 + m0, m0) - C(n0 + m0, m0 - 1) + mod) % mod * C(n0 + m0 + i, i) % mod) %= mod;
        } printf("%lld\n", ans);
    } return 0;
}