第二道问号题。
设 \(A \ge B\)。我们现在将点的坐标刻画到二维平面上。相当于找到一条 \((0, 0) \to (A, B)\) 的路径,要求不能跨过直线 \(y = x\)。有 \(3\) 种移动方式:
- 向右移动一格。
- 向上移动一格。
- 将当前点提到直线 \(y = x\) 上,也就是将 \(y\) 坐标赋值为 \(x\) 坐标。
为了避免算重,其中 \(2\) 操作要求向上移动一格后,点不能在直线 \(y = x\) 上。
若不使用操作 \(3\) 答案是好算的。相当于找到一条 \((1, 0) \to (A, B)\) 的不接触直线 \(y = x\) 的一条路径,考虑容斥,将任意一条与直线 \(y = x\) 有交的路径的最后一个交点拿出来,把这之前的部分沿直线 \(y = x\) 翻转,可以发现有交点的方案数就是 \((0, 1) \to (A, B)\) 的方案数。所以无交点的方案数是 \(\binom{A + B - 1}{A - 1} - \binom{A + B - 1}{A}\)。
若使用操作 \(3\),考虑相对运动,将把点提到直线 \(y = x\) 上,变成将直线拉到 \(y = x - k\)。设在点 \((x_0, y_0)\) 最后一次使用操作 \(3\),设 \(k = x_0 - y_0\),那么我们的终点是 \((A, B - k)\),直线最终位于 \(y = x - k\)。
考虑分配除了最后一次的操作 \(3\)。我们确定了一条 \((1, 0) \to (A, B - k)\) 的折线后,一个点 \((x, x - d)\) 可以使用操作 \(3\) 当且仅当这个点是直线 \(y = x - d\) 与折线的最后一个交点。发现 \(d = 0, 1, \ldots, k\) 都唯一对应一个点。于是我们把 \(n - A - (B - k) - 1\) 次操作 \(3\)(减 \(1\) 是因为 \(d = k\) 至少要使用一次操作 \(3\))分配到这 \(k + 1\) 个点上,插板算即可。
code
// Problem: F - Two Pieces
// Contest: AtCoder - AtCoder Grand Contest 040
// URL: https://atcoder.jp/contests/agc040/tasks/agc040_f
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 20000100;
const int N = 20000000;
const ll mod = 998244353;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, A, B, fac[maxn], ifac[maxn];
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
inline ll F(ll n, ll m) {
return (C(n + m - 1, n - 1) - C(n + m - 1, n) + mod) % mod;
}
void solve() {
scanf("%lld%lld%lld", &n, &B, &A);
fac[0] = 1;
for (int i = 1; i <= N; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
ifac[N] = qpow(fac[N], mod - 2);
for (int i = N - 1; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
if (A == 0 && B == 0) {
puts("1");
return;
}
ll ans = (A + B == n ? F(A, B) : 0);
for (int i = 0; i <= B; ++i) {
ll r = n - A - (B - i);
ans = (ans + F(A, B - i) * C(r - 1 + i, i)) % mod;
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- AtCoder Contest Pieces Grand 040atcoder contest grand 040 atcoder contest pieces grand authentic atcoder contest grand negative atcoder contest grand atcoder contest radius grand atcoder contest grand 001 atcoder contest grand 022 avoidance atcoder contest grand histogram atcoder contest grand atcoder contest grand 019