:::info[Description] Link. :::
:::infoSolution 考虑从给一个初始状态调整维护答案的变化量。把路径看作是一个长度为 的 序列，其中 代表向上移动， 代表向右移动。初始状态就是 个 拼接上 个 得到的序列。
考虑把一对相邻的 修改成 。简单算一下可知路径权值的变化量就是 （若两个位置分别是第 次移动和第 次移动）。进一步调整后发现满足条件的 序列必然满足下标为偶数位置上的 的数量恰为 。这个东西直接组合数算就行，最终答案就是 。预处理阶乘和阶乘逆可做到线性时间复杂度。 :::
:::success[Code]
namespace lowspeed_song {
int fac[N], inv[N], ifac[N];
inline void init() {
fac[0] = inv[0] = ifac[0] = 1;
fac[1] = inv[1] = ifac[1] = 1;
for (int i = 2; i < N; ++i) {
fac[i] = fac[i - 1] * i % mod;
inv[i] = mod - inv[mod % i] * (mod / i) % mod;
ifac[i] = ifac[i - 1] * inv[i] % mod;
}
}
inline int binom(int a, int b) {
if (b < 0 || a < b) return 0;
return fac[a] * ifac[b] % mod * ifac[a - b] % mod;
}
inline void sol() {
int n, m, k; cin >> n >> m >> k;
cout << binom((n + m) / 2, k + n / 2) * binom((n + m + 1) / 2, n - k - n / 2) % mod << '\n';
}
} // namespace lowspeed_song:::
难度：紫-
鲜活指数：6
喜欢的话，留下你的评论吧～