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

_Genius_ · 2026-08-07 21:09:28 · 题解

写一篇详细一点的题解。

注：本篇文章使用 deepseek 润色。

题意转化

设选出的 m 个元素构成集合 S，则“任意两数差不超过 t”等价于：

即所有元素必须落在某个长度不超过 t 的区间内。

前置知识（上指标求和公式）

上指标求和指的是对组合数的上标进行累加求和，常用公式为曲棍球恒等式（朱世杰恒等式）：

证明

我们知道组合数有一个递推公式：\binom{i}{a} = \binom{i - 1}{a} + \binom{i - 1}{a - 1}，变形一下，有：

再移项：

有：

这玩意显然可以裂项相消：

因为 \binom{a}{a + 1} = 0，所以：

变种

上指标求和公式有很多变种，这里给出我们下文要用到的：

同样可以裂项证明。

解题思路

25 分

枚举最小值 a，剩余 m-1 个数只能从 [a+1,\ \min(a+t,n)] 中选取。若不排除 x，组合数为：

每个组合可排列成 m! 个序列。若排除 x，当 x 落在可选区间内时，可选个数减 1，即：

答案即为：

100 分

考虑容斥，设：

则答案为：

\text{Part 1}

通过前面的推导我们可以得到一个求和式：

我们发现可以分讨来拆掉 \min(t, \ n - a)。

情况 1

当 a\le n-t 时，\min(t,\ n-a)=t，贡献为：

情况 2

当 a>n-t 时，\min(t,\ n-a)=n-a，贡献为：

换元，令 p = n - a。因为 n - t + 1 \leq a \leq n，所以 0 \leq p \leq t - 1，所以上述求和式等价于：

由曲棍球恒等式（不会的看前置知识），得：

因此：

\text{Part 2}

我们同样根据最小值 a 来分讨。

情况 1

当 a = x 时，贡献为：

情况 2

当 a<x 且 a\le n-t 时，因为 a\ge x-t，所以：

设 A=\max(1,\ x-t)，B=x-1，合法 a 的个数为：

每个 a 对应方案数：\binom{t-1}{m-2}（排除掉 a 和 x 我们还有 t - 1 个数可以选，m - 2 个位置要填），因此：

情况 3

当 a<x 且 a>n-t 时，实际区间为 [a,n]，因为必须包含 x，所以有：

每个 a 的方案数为（排除掉 x 和 a 还有 n - a - 1 个数可以选，有 m - 2 个位置要填）：

总和为：

换元，令 p=n-a，有：

利用曲棍球恒等式的变种，得：

而 n-\max(A,\ n-t+1)=\min(n-A,\ t-1)，n - B - 1 = n - x，代入得：

最终答案

代码实现

注意一下边界即可。

::::success[25 分]

#include <bits/stdc++.h>
#define i64 long long
using namespace std;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
vector<i64> fac(N, 0), inv(N, 0);
i64 qpow(i64 base, int b) {
    i64 res = 1;
    while (b) {
        if (b & 1) res = res * base % mod;
        base = base * base % mod;
        b >>= 1;
    }
    return res;
}
i64 C(int x, int y) {
    if (x - y < 0) return 0;
    if (!y || !(x - y)) return 1;
    return ((fac[x] * inv[y] % mod) * inv[x - y]) % mod;
}
int in(int l, int r, int x) {
    return l <= x && x <= r;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    fac[0] = 1;
    for (int i = 1; i < N; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    inv[N - 1] = qpow(fac[N - 1], mod - 2);
    for (int i = N - 2; i >= 1; i--) {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
    int n, m, q;
    cin >> n >> m >> q;
    while (q--) {
        int x, t;
        cin >> x >> t;
        i64 ans = 0;
        for (int i = 1; i <= n; i++) {
            if (i == x) continue;
            int a = min(n - i - in(i, n, x), t - in(i, i + t, x));
            int b = m - 1;
            i64 c = fac[m];
            ans = (ans + (C(a, b) * c % mod)) % mod;
        }
        cout << ans << "\n";
    }
    return 0;
}

:::: ::::success[100 分]

#include <bits/stdc++.h>
#define i64 long long
using namespace std;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
vector<i64> fac(N, 0), inv(N, 0);
inline i64 qpow(i64 base, int b) {
    i64 res = 1;
    while (b) {
        if (b & 1) res = res * base % mod;
        base = base * base % mod;
        b >>= 1;
    }
    return res;
}
inline i64 C(int x, int y) {
    if (x < 0 || y < 0 || x - y < 0) return 0;
    if (!y || !(x - y)) return 1;
    return ((fac[x] * inv[y] % mod) * inv[x - y]) % mod;
}
inline int in(int l, int r, int x) {
    return l <= x && x <= r;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    fac[0] = 1;
    for (int i = 1; i < N; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    inv[N - 1] = qpow(fac[N - 1], mod - 2);
    for (int i = N - 2; i >= 1; i--) {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
    int n, m, q;
    cin >> n >> m >> q;
    while (q--) {
        int x, t;
        cin >> x >> t;
        int A = max(1, x - t), B = x - 1;
        i64 S = (((n - t) * C(t, m - 1) % mod) + C(t, m)) % mod;
        i64 E1 = C(min(t, n - x), m - 1);
        i64 C1 = max(0, min(B, n - t) - A + 1) * C(t - 1, m - 2) % mod;
        i64 C2 = 0;
        if (max(A, n - t + 1) <= B) {
            C2 = (C(min(n - A, t - 1), m - 1) - C(n - x, m - 1) + mod) % mod;
        }
        i64 ans = ((((S - E1 - C1 - C2) % mod) + mod) % mod) * fac[m] % mod;
        cout << ans << "\n";
    }
    return 0;
}

::::