喵~ 主人，欢迎来到本喵的解题小课堂！今天我们要看的是一道关于跳舞的题目，Ira 和她的弗拉明戈舞会，听起来就很有趣呢，嘻嘻~ (ฅ'ω'ฅ)

这道题是 Codeforces 上的 1833F，让本喵带你一步一步把它拿下吧！

题目大意喵

伊拉 (Ira) 老师有 n 个学生，每个学生都有一个舞蹈水平 a_i。她想要从中挑选一些学生来表演一场 “华丽的舞蹈”。

一场舞蹈被称为“华丽的”，需要同时满足下面三个条件哦：

1. 人数固定：必须正好有 m 个学生参加。
2. 水平各异：参加舞蹈的学生，他们的舞蹈水平必须是两两不同的。
3. 水平接近：任意两个参加舞蹈的学生，他们的水平差的绝对值必须 严格小于 m。

我们的任务就是，计算伊拉老师总共能组织多少种不同的“华丽的舞蹈”。因为答案可能会很大，所以要对 10^9 + 7 取模。

注意哦，只要参加的学生集合不一样，就算作是两种不同的舞蹈。

举个例子，如果 m=3，学生水平是 [4, 2, 2, 3, 6]。

• 选水平为 2, 3, 4 的学生就是一场华丽的舞蹈，因为人数是3，水平各不相同，而且最大差值 |4-2|=2，小于 m=3。
• 但如果选水平为 3, 4, 6 的学生，就不是华丽的了，因为 |6-3|=3，没有严格小于 m。

是不是听起来有点绕喵？没关系，让本喵来给你理一理思路！

解题方法喵

要把这道题解开，关键是把那三个条件转化成我们可以处理的形式，喵~

1. 条件 1 和 2：m 个学生，水平各不相同。 这告诉我们，我们首先需要从所有学生中，选出 m 个 不同的 舞蹈水平。如果总共的独特水平数量都不到 m 个，那肯定一种方案都组不出来啦。

2. 条件 3：任意两名舞者的水平差 |level_i - level_j| < m。 这个条件看起来最麻烦，要检查每一对舞者。但是喵，这里有个小技巧！如果我们把选出来的 m 个不同的水平从小到大排个序，比如 l_1 < l_2 < ... < l_m，那么这个条件其实就等价于一个更简单的条件： l_m - l_1 < m 为什么呢？因为 l_m - l_1 已经是这 m 个水平中的最大差值了。如果连最大的差值都小于 m，那其他任意一对水平的差值肯定也小于 m 啦！是不是很机智喵？(＾ω＾)

好啦，现在思路就清晰多啦！我们的解题步骤就像猫猫捕食一样，分三步走：

第一步：预处理 先把所有学生的水平值和他们对应的人数统计出来。用 std::map 或者哈希表来做最方便了，key 是水平值，value 是该水平的学生数量。然后，我们把所有独特的水平值取出来，放进一个数组 unique_levels 里，并排好序。

第二步：滑动窗口 既然我们要在排好序的 unique_levels 中找到一段连续的 m 个水平，满足 最大值 - 最小值 < m，这不就是经典的 滑动窗口 问题嘛！

我们可以维护一个大小为 m 的窗口，在 unique_levels 数组上从左到右滑动。

• 窗口的左边界是 j，右边界是 i，窗口大小为 m，所以 i - j + 1 = m。
• 对于每个窗口，我们检查 unique_levels[i] - unique_levels[j] < m 是否成立。

第三步：计算方案数 如果当前窗口 [j, i] 满足条件，那么我们就找到了一个可行的水平组合 (unique_levels[j], unique_levels[j+1], ..., unique_levels[i])。

接下来就要计算用这些水平能组成多少种不同的学生队伍。 假设水平 unique_levels[k] 有 count[k] 个学生。根据乘法原理，总的组合数就是： count[j] * count[j+1] * ... * count[i]

我们把所有满足条件的窗口算出来的组合数全部加起来，就是最终的答案啦。

优化一下喵！ 每次滑动窗口都重新计算一遍乘积，太慢了喵！m 可能很大，这样会超时的。 我们可以用 前缀积 来优化。先预处理一个 prefix_prods 数组，其中 prefix_prods[i] 存储从第 0 个独特水平到第 i 个独特水平的人数之积。 prefix_prods[i] = count[0] * count[1] * ... * count[i]

这样，窗口 [j, i] 的乘积就可以通过 prefix_prods[i] / prefix_prods[j-1] 来快速计算。 但是，我们是在模 10^9 + 7 的意义下计算的，除法要用 模逆元 来实现。a / b % MOD 就变成了 a * b^(MOD-2) % MOD。

总结一下最终的算法：

1. 用 map 统计每个水平的人数。
2. 如果独特水平数小于 m，答案为 0。
3. 将独特水平和对应人数分别存入 vector，并对水平排序（map 自动排序了，直接提取即可）。
4. 计算人数的 前缀积 数组。
5. 使用大小为 m 的滑动窗口遍历独特水平数组。
6. 对每个窗口，检查 max_level - min_level < m。
7. 如果满足，利用前缀积和模逆元计算该窗口的方案数，并累加到总答案中。
8. 输出总答案。

题解代码详解

这是本喵根据上面的思路写的 C++ 代码，加了一些注释方便主人理解哦~

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

// MOD 常量，题目要求哒
const int MOD = 1000000007;

// 快速幂函数，用来求 (base^exp) % MOD
// 这是计算模逆元的基础喵
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 solve() {
    int n, m;
    std::cin >> n >> m;
    // 用 map 来统计每个等级有多少个学生，它会自动按键（等级）排序，很方便喵
    std::map<int, int> counts;
    for (int i = 0; i < n; ++i) {
        int a;
        std::cin >> a;
        counts[a]++;
    }

    // 如果独特的等级数量连 m 个都不到，那肯定组不成舞会啦，直接返回 0
    if (counts.size() < m) {
        std::cout << 0 << std::endl;
        return;
    }

    // 把 map 里的键（等级）和值（数量）分别抽出来放到 vector 里
    // 这样用下标访问会比 map 快很多，方便滑动窗口操作
    std::vector<int> unique_levels;
    std::vector<long long> level_counts;
    unique_levels.reserve(counts.size());
    level_counts.reserve(counts.size());
    for (auto const& [level, count] : counts) {
        unique_levels.push_back(level);
        level_counts.push_back(count);
    }

    int k = unique_levels.size();
    
    // 秘密武器——前缀积数组！
    // prefix_prods[i] 存的是前 i+1 个等级数量的乘积（模 MOD）
    std::vector<long long> prefix_prods(k);
    prefix_prods[0] = level_counts[0];
    for (int i = 1; i < k; ++i) {
        prefix_prods[i] = (prefix_prods[i - 1] * level_counts[i]) % MOD;
    }

    long long total_ways = 0;
    
    // 开始滑动窗口！窗口大小为 m
    // i 是窗口的右边界，从 m-1 开始
    for (int i = m - 1; i < k; ++i) {
        int j = i - (m - 1); // j 是窗口的左边界

        // 检查这个窗口是不是一个“华丽”的组合
        // 也就是最大等级和最小等级的差是不是严格小于 m
        if (unique_levels[i] - unique_levels[j] < m) {
            // 条件满足！计算这个窗口的组合数
            // 组合数是窗口内所有等级对应人数的乘积
            long long ways_for_window = prefix_prods[i];
            if (j > 0) {
                // 如果左边界不是数组开头，就要除以前面的部分
                // 除以 prefix_prods[j-1] 等价于乘以它的模逆元
                long long inv = modInverse(prefix_prods[j - 1]);
                ways_for_window = (ways_for_window * inv) % MOD;
            }
            // 把当前窗口的方案数加到总数上，别忘了取模哦喵
            total_ways = (total_ways + ways_for_window) % MOD;
        }
    }

    std::cout << total_ways << std::endl;
}

int main() {
    // 加速输入输出，是个好习惯喵
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

知识点小鱼干

学完一道题，当然要吃点知识点小鱼干巩固一下啦！(๑>ڡ<)

1. 滑动窗口 (Sliding Window)

   • 是什么：滑动窗口是一种非常高效的算法技巧，常用于解决数组或字符串的子区间问题。它就像一个固定大小的窗户，在序列上从头到尾滑动，每次移动一步，从而在 O(N) 的时间复杂度内处理所有子区间。
   • 为什么用：这道题需要我们考察所有长度为 m 的连续独特水平序列，滑动窗口是完美匹配这个场景的工具。

2. 前缀积 (Prefix Product)

   • 是什么：和我们熟悉的前缀和类似，前缀积数组 P 的第 i 个元素 P[i] 存储的是原数组从 A[0] 到 A[i] 的所有元素的乘积。
   • 为什么用：它能让我们在 O(1)（或者计算模逆元的 O(log M)）时间内求出任意区间的乘积，避免了在滑动窗口中每次都进行 O(m) 的重复计算，大大提升了效率。

3. 模运算与模逆元 (Modular Arithmetic & Modular Inverse)

   • 是什么：当计算结果非常大，超过了标准数据类型的表示范围时，我们通常需要对一个固定的数（模数，MOD）取余。这就是模运算。
   • 模逆元：在模运算中，加、减、乘法都保持良好性质，但除法不行。(A / B) % M 并不等于 (A % M / B % M)。为了在模意义下做除法，我们引入了模逆元。B 的模逆元 B⁻¹ 满足 (B * B⁻¹) % M = 1。于是，除以 B 就变成了乘以 B 的模逆元：(A / B) % M = (A * B⁻¹) % M。
   • 怎么求：当模数 M 是一个质数时（这道题的 10^9 + 7 就是质数），我们可以用 费马小定理 快速求出逆元：B^(M-2) % M 就是 B 的模逆元。计算 B^(M-2) 可以用 快速幂 算法高效完成。

好啦，今天的讲解就到这里喵~ 主人有没有觉得这道题变得简单可爱了呢？下次再遇到类似的问题，可要想起本喵的滑动窗口和前缀积小技巧哦！我们下次再见啦，喵~ (づ｡◕‿‿◕｡)づ