自动搬运

查看原文

来自洛谷，原作者为

	Su777 CSP 2025 勾七

搬运于2025-08-24 23:10:05，当前版本为作者最后更新于2025-02-22 21:14:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

【背景】

看了眼榜，发现 D 的通过率出奇地高，于是顺手切掉了。个人认为中位绿。

【题意】

在 $[1,n]$ 的正整数中选择 $m$ 个，不能选择 $x$，选择的任何两个数相差不能超过 $t$，求方案数。

【解法】

从最后一个条件（任何两个数相差不能超过 $t$）入手，我们可以把整个问题分解：

• 在 $[1,1+t]$ 的正整数中选择 $m$ 个，不能选择 $x$。
• 在 $[2,2+t]$ 的正整数中选择 $m$ 个，不能选择 $x$。
• ……
• 在 $[n-t,n]$ 的正整数中选择 $m$ 个，不能选择 $x$。

这个最难的条件就被我们分解掉了。每个子问题很简单，如果区间包含 $x$，答案即为 $t \choose m$；如果区间不包含 $x$，答案即为 $t+1 \choose m$。组合数使用阶乘逆元计算。

注意各个子问题的答案不能简单相加。相邻的两个子问题会出现算重的情况（注意 $t=m-1$ 时下面这些子问题的方案数均为 $0$，需要特判），这时候我们再减去下面这些子问题的答案：

• 在 $[2,1+t]$ 的正整数中选择 $m$ 个，不能选择 $x$。
• 在 $[3,2+t]$ 的正整数中选择 $m$ 个，不能选择 $x$。
• ……
• 在 $[n-t,n-1]$ 的正整数中选择 $m$ 个，不能选择 $x$。

就可以得到最终答案，但是会 TLE。暴力代码在这里。考虑优化。

其实，我们不需要枚举所有的区间。只需要通过简单的推导算出这些值：

• 长度为 $t+1$ 且包含 $x$ 的区间数量，设为 $a$。
• 长度为 $t+1$ 且不包含 $x$ 的区间数量，设为 $b$。
• 长度为 $t$ 且包含 $x$ 的区间数量，设为 $c$。
• 长度为 $t$ 且不包含 $x$ 的区间数量，设为 $d$。

根据上述推理，最终答案可以表示为 $a\times {t\choose m} + b\times {t+1\choose m}-c\times{t-1\choose m}-d\times{t\choose m}$，相当于拆贡献，正确性显然。

【代码】

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod = 1e9 + 7;
const ll M = 2e5 + 10;
ll fac[M], inv[M];
ll qpow(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1ll) res = res * a % mod;
		a = a * a % mod; b >>= 1;
	}
	return res % mod;
}
ll C(ll n, ll m) {
	return fac[n] % mod * inv[m] % mod * inv[n - m] % mod;
}

int main() {
	fac[0] = 1;
	inv[0] = 1;
	for (ll i = 1; i <= 200000; i ++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = qpow(fac[i], mod - 2);
	}
    ll n, m, q;
    cin >> n >> m >> q;
    while (q--) {
        ll x, t, ans = 0;
        cin >> x >> t;
        ll all = n - t, have_x_cnt = 0;
        have_x_cnt = (min(n, x + t) - t) - (max(1ll, x - t)) + 1;
        ans += have_x_cnt % mod * C(t, m) % mod; ans %= mod;
        ans += (all - have_x_cnt) % mod * C(t + 1, m) % mod;
        ans %= mod;

        all = (n - t) - 2 + 1, have_x_cnt = 0;
        have_x_cnt = (min(n - 1, x + t - 1) - (t - 1)) - max(2ll, x - (t - 1)) + 1;
        if (t - 1 >= m) ans = (ans + mod - have_x_cnt * C(t - 1, m)) % mod;
        ans = (ans + mod) % mod;
        ans = (ans + mod - (all - have_x_cnt) * C(t, m)) % mod;
        ans = (ans + mod) % mod;
        ans = ans % mod * fac[m] % mod;
        cout << ans << "\n";
    }
    return 0;
}