CF1462-E2. Close Tuples (hard version)

本题为hard版，还有一个easy版，区别在于k和m的取值不同。

题意：

给出一个由n个数字组成的数组 \(a\)。现在定义一种子集为\(\{A_1, A_2, A_3, ..., A_m\}\)，使得这个子集中的最大值和最小值的差值不超过k，其中m和k是给出的。现在问你这种子集有几个。

思路：

对给出的数组进行排序，用\(for\)循环枚举子集中的\(A_1\)，之后用upper_bound找到数组中第一个数字，使得这个数字减去\(A_1\)大于k。若这个数字和\(A_1\)之间元素的个数大于\(m - 1\)，那么利用组合数\(C_n^m\)就可以求出部分答案。最后将每一部分的答案加起来就可以得到最终答案。

额外知识：

由于题目要求取模，但是组合数中却有除法，不能直接取模，所以需要用到逆元。组合数取模板子

AC代码（直接用板子）：

#include <cstdio>

#include <algorithm>

#include <iostream>

const int N = 2e5 + 5;

const int mod = 1e9 + 7;

typedef long long ll;

ll f[N];

ll qpow(ll a, ll b) {

    ll ans = 1, base = a;

    while (b) {

        if (b & 1) ans = ans * base % mod;

        base = base * base % mod;

        b >>= 1;

    }

    return ans;

}

void init() {

    f[0] = 1;

    for (int i = 1; i <= 2e5; i++) {

        f[i] = f[i - 1] * i % mod;

    }

}

ll cal(ll n, ll m) {

    if (n < m) return 0;

    return 1ll * f[n] * qpow(f[m], mod - 2) % mod * qpow(f[n - m], mod - 2) % mod;

}

int a[N];

int main () {

    init();

    int T, n, m, k;

    scanf ("%d", &T);

    while (T--) {

        scanf ("%d %d %d", &n, &m, &k);

        for (int i = 0; i < n; i++) {

            scanf ("%d", &a[i]);

        }

        std::sort (a, a + n);

        int p = 0;

        ll ans = 0;

        for (int i = 0; i < n; i++) {

            p = (int)(std::upper_bound(a, a + n, a[i] + k) - a);

            if (p - i >= m) {

                ans = ans + cal(p - i - 1, m - 1);

                ans = ans % mod;

            }

        }

        printf ("%lld\n", ans);

    }

    return 0;

}

巴特西

CF1462-E2. Close Tuples (hard version)

题意：

给出一个由n个数字组成的数组 \(a\)。现在定义一种子集为\(\{A_1, A_2, A_3, ..., A_m\}\)，使得这个子集中的最大值和最小值的差值不超过k，其中m和k是给出的。现在问你这种子集有几个。

思路：

额外知识：

由于题目要求取模，但是组合数中却有除法，不能直接取模，所以需要用到逆元。组合数取模板子

AC代码（直接用板子）：

最新文章

热门文章

巴特西

CF1462-E2. Close Tuples (hard version)

题意：

给出一个由n个数字组成的数组 \(a\)。现在定义一种子集为\(\{A_1, A_2, A_3, ..., A_m\}\)，使得这个子集中的最大值和最小值的差值不超过k，其中m和k是给出的。现在问你这种子集有几个。

思路：

额外知识：

由于题目要求取模，但是组合数中却有除法，不能直接取模，所以需要用到逆元。 组合数取模板子

AC代码（直接用板子）：

最新文章

热门文章

由于题目要求取模，但是组合数中却有除法，不能直接取模，所以需要用到逆元。组合数取模板子