自动搬运

查看原文

来自洛谷，原作者为

	Link_Cut_Y 菜就多练

搬运于2025-08-24 22:06:11，当前版本为作者最后更新于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$，答案即为：

$$\binom{n' + m'}{m'} - \binom{n' + 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;
}