题解：P11767 「KFCOI Round #1」缥缈

· · 题解

【背景】

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

【题意】

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

【解法】

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

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

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

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

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

根据上述推理，最终答案可以表示为 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;
}