E2. Close Tuples (hard version) - 题解

比赛与标签

比赛: Codeforces Round 690 (Div. 3) 标签: binary search, combinatorics, implementation, math, sortings, two pointers 难度: *1700

题目大意喵~

主人，我们收到了一个有趣的挑战任务，喵~！

任务是这样的：给定一个长度为 n 的序列 a，以及两个整数 m 和 k。我们需要从序列 a 中找出 m 个数，组成一个元组（tuple）。这个元组需要满足一个特殊的条件：元组中最大的数减去最小的数，差值不能超过 k。

我们的目标，就是计算出有多少种不同的方法可以选择这 m 个数的下标，使得它们对应的值满足上面的条件。因为答案可能会非常非常大，所以需要对 10^9 + 7 取模哦！

举个栗子：如果 a = [1, 2, 4, 3]，m = 3，k = 2。 我们可以选择下标 {1, 2, 4}，对应的值是 {1, 2, 3}。最大值是3，最小值是1，差是 3 - 1 = 2，满足 2 <= k。 我们还可以选择下标 {2, 3, 4}，对应的值是 {2, 4, 3}。最大值是4，最小值是2，差是 4 - 2 = 2，也满足 2 <= k。 所以总共有 2 种符合条件的元组，喵~

解题思路详解，Nya~

看到这个问题，第一反应可能是暴力枚举所有 m 个数的组合，但这太慢啦，肯定会超时的说！我们需要更聪明的办法，喵~ 让我们一步步来拆解这个问题吧！

第一步：排序！排序是魔法的开始！

题目的条件是 max(a_i) - min(a_i) <= k。这个条件只和数值有关，和它们原来的位置无关。这种时候，排序通常是我们的好朋友！

我们先把数组 a 从小到大排个序。排序之后，对于任意一个我们选出的元组，它的最小值就是最左边的元素，最大值就是最右边的元素。这样一来，问题就清晰多啦！

第二步：换个角度看问题

直接去数元组还是很麻烦。不如我们换个思路：我们遍历数组中的每一个元素 a[i]，然后思考：有多少个符合条件的元组，其最大值恰好是 a[i] 呢？

如果我们能对每个 a[i] 都算出这个数量，再把它们全部加起来，不就是总答案了嘛？而且，因为我们是按排序后的数组来选最大值的，所以每个元组只会被它的最大值（以及最右边的那个最大值）统计一次，不会重复计算，完美~

第三步：双指针的优雅华尔兹

好，现在我们的目标是：固定 a[r] 作为元组的最大值，找出其他 m-1 个元素。

这些元素需要满足什么条件呢？它们必须小于等于 a[r]，并且大于等于 a[r] - k。

由于数组已经排好序了，所有在 a[r] 左边的元素都小于等于 a[r]。我们只需要找到一个最左边的位置 l，使得 a[l] >= a[r] - k。这样一来，从 a[l] 到 a[r-1] 之间的所有元素，都可以和 a[r] 一起组成一个满足条件的元组！

这不就是经典的双指针（或者叫滑动窗口）模型嘛！

1. 我们用一个指针 r 从左到右遍历整个数组，a[r] 是我们当前考虑的元组最大值。
2. 我们用另一个指针 l 维护一个区间的左端点。
3. 当 r 向右移动时，a[r] 变大，a[r] - k 也变大。所以，为了满足 a[l] >= a[r] - k，l 指针也只可能向右移动，绝不会向左。这就是双指针能够高效工作的关键——单调性！

对于每个 r，我们移动 l 直到 a[r] - a[l] <= k。此时，在 a[r] 的左边，从 a[l] 到 a[r-1]，一共有 r - l 个元素。这些元素都是我们可以选择的“小伙伴”。

第四步：组合数学来帮忙！

我们已经确定了最大值是 a[r]，并且找到了 r - l 个可以和它搭配的候选元素。我们需要从这 r - l 个候选元素中，再挑选出 m-1 个，来凑成一个大小为 m 的元组。

这不就是高中数学里的组合问题嘛！从 N 个不同元素中选出 R 个，方案数是 C(N, R)。 所以，对于固定的 a[r]，新增加的元组数量就是 C(r - l, m - 1)。

我们只需要在 r 遍历的过程中，不断累加这个组合数就可以啦。

总结一下思路：

1. 预处理：因为要算组合数 C(n, r) 并且取模，我们可以提前计算好阶乘和阶乘的逆元。这样每次计算组合数就非常快了。
2. 排序：将数组 a 升序排列。
3. 双指针：初始化左右指针 l = 0, r = 0。
4. 遍历与计算：
   • 外层循环 r 从 0 到 n-1。
   • 内层 while 循环，当 a[r] - a[l] > k 时，l 向右移动。
   • 此时，我们有 r - l 个候选元素（下标从 l 到 r-1）。
   • 从这 r - l 个元素中选 m - 1 个，方案数为 C(r - l, m - 1)。
   • 将这个方案数累加到总答案 total_count 中。
5. 输出：最后输出 total_count 就好啦！

代码实现喵~

#include <iostream>
#include <vector>
#include <algorithm>

// 快速 I/O，让程序跑得更快喵~
void setup_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

const int MOD = 1e9 + 7;
const int MAX_N_SUM = 200005; // 所有测试用例n的总和最大值

// 预先计算阶乘和阶乘的逆元，方便后面算组合数
long long fact[MAX_N_SUM];
long long invFact[MAX_N_SUM];

// 快速幂，用来求逆元，(a^(p-2)) % p 就是 a 在模 p 下的逆元
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 求模逆元
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

// 预处理阶乘和逆元数组
void precompute_factorials() {
    fact[0] = 1;
    for (int i = 1; i < MAX_N_SUM; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    // 先算出最大数的阶乘逆元
    invFact[MAX_N_SUM - 1] = modInverse(fact[MAX_N_SUM - 1]);
    // 然后倒着推回来，因为 (inv(n!)) * n = inv((n-1)!)
    for (int i = MAX_N_SUM - 2; i >= 0; i--) {
        invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
    }
}

// 计算组合数 C(n, r) % p
long long nCr_mod_p(int n, int r) {
    // 如果 r > n 或者 r < 0，组合无意义，返回0
    if (r < 0 || r > n) {
        return 0;
    }
    // C(n,r) = n! / (r! * (n-r)!)
    // 模意义下，除法变成乘以逆元
    return (((fact[n] * invFact[r]) % MOD) * invFact[n - r]) % MOD;
}

void solve() {
    int n;
    int m;
    int k;
    std::cin >> n >> m >> k;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    
    // 魔法的第一步：排序！
    std::sort(a.begin(), a.end());
    
    long long total_count = 0;
    int l = 0; // 左指针
    // r 是右指针，代表我们当前考虑的元组的最大值
    for (int r = 0; r < n; ++r) {
        // 移动左指针，直到窗口内的差值满足条件
        // a[r] - a[l] <= k
        while (a[r] - a[l] > k) {
            l++;
        }
        
        // 现在，a[r]是最大值，其他 m-1 个元素可以从 a[l]...a[r-1] 中选择
        // 候选元素的数量是 (r-1) - l + 1 = r - l
        int candidates = r - l;
        
        // 如果候选人的数量足够我们选 m-1 个
        if (candidates >= m - 1) {
            // 计算 C(candidates, m-1) 并累加到总数
            total_count = (total_count + nCr_mod_p(candidates, m - 1)) % MOD;
        }
    }
    
    std::cout << total_count << "\n";
}

int main() {
    setup_io();
    // 全局只做一次预处理，效率更高
    precompute_factorials();
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析的说

• 时间复杂度: O(S + Σ(n log n)) 的说。

  • S 是预处理阶乘数组的时间，S 等于 MAX_N_SUM，所以这部分是 O(MAX_N_SUM)。
  • Σ(n log n) 是所有测试用例排序时间的总和。
  • 对于每个测试用例，双指针部分的时间复杂度是 O(n)，因为 l 和 r 指针都只从头到尾走了一遍。
  • 所以总的时间瓶颈在于预处理和排序。

• 空间复杂度: O(MAX_N_SUM) 的说。

  • 我们需要 O(MAX_N_SUM) 的空间来存储阶乘和阶乘逆元数组。
  • 每个测试用例中，存储数组 a 需要 O(n) 的空间。
  • 空间主要被预处理的数组占用了。

知识点与总结喵~

这个题目真是个小宝库，融合了好几个重要的知识点呢！

1. 排序思想: 遇到涉及元素大小比较、差值、区间的题目，排序往往是打开思路的第一把钥匙！它能将无序的问题变得有序，从而利用其单调性。
2. 双指针技巧: 对于在有序序列上寻找满足特定条件的子序列或数对，双指针是极其高效的算法。关键在于找到指针移动的单调性，确保它们永不后退，从而达到线性时间复杂度。
3. 组合计数: 当问题涉及到“从 N 个里选 R 个”且不关心顺序时，就要想到组合数 C(N, R)。
4. 模运算与逆元: 在处理需要取模的大数计数问题时，加减乘法可以直接取模，但除法需要转换为乘以模逆元。对于质数模，使用费马小定理 a^(p-2) 是求逆元的常用方法。
5. 预处理: 对于需要反复计算的数值（比如本题的组合数），通过一次性的预处理（计算阶乘），可以大大加快后续每次计算的速度。

总之，解题就像一场探险，先用排序整理好地图，然后派上双指针这对好搭档去探索，最后用组合数学的魔法棒点石成金，就得到答案啦！主人，你学会了吗？继续加油，你一定能成为超厉害的算法大师的，喵~！