本文使用 $\LaTeX$ 语法。若出现渲染失败或错误,请刷新页面并耐心等待刷新完成。

CF1462E2 Close Tuples (hard)

先来一句废话:这题的翻译是我写的欸!!

本文同步于蒟蒻的洛谷博客

还是组合数

分析

首先恶心人的是这是道纯英文的题的题意(你没看错,还是这句话)。借助一些奇怪的手段(指盲猜),我们可以明白这题面的意思是

给定 $t$ 个长为 $n$ 的数组 $a$,取元素个数为 $m$ 的数组 ${b}\in a$ 满足其中元素各不相同,使得 $num_1,num_2 \in b$ 满足 $max(num_1)-min(num_2)\leqslant k$,问最多能找出多少组,并取模 $10^9+7$。

想到是组合数之后,本想一发 sort 之后从头开始求区间的组合,但是偶发现有问题,由于数据可能重复,于是复杂度增加亿点点。

如数据 $1, 2, 3, 3, 4$ 按上述方法就是 $cnt$ 先加上 $1 \sim 3$ 之间的组合数,求完之后再加上 $2 \sim 4$ 之间的组合数,但是 $1 \sim 3$ 之间的 $2, 3, 3$ 和 $2 \sim 4$ 之间的 $2, 3, 3$ 重复了。于是卡了一节课 窝太菜了

后经学长点拨,在排序后先取一个值 $a_i$,再在 $( a_i,a_i+2 ]$ 范围内取两个值,便可以避免重复。(妙哉!)

例如,求 $1 \sim 3$ 时,取最小值 $1$,在 $( 1 , 3 ]$ 区间内(即 $2 ,3 ,3$)任取两个值;

接着求 $2 \sim 4$ 时,取最小值 $2$,在 $( 2 , 4 ]$ 区间内任取两个值。

不难看出,以上情况无重复。

易得,求 $(a_i, a_i+k ]$ 同理。

想清楚原理后就不难实现了

记得开 long long!

实现

贴核心代码:


const int N = 200005;
const int md = 1000000007;

int a[N];
ll f[N];
ll qpow(ll a, ll b) {  //快速幂
    ll ans = 1, base = a;
    while(b){
        if(b&1)ans=ans*base%md; 
        base=base*base%md;
        b>>=1;
    }
    return ans;
}
ll ght(ll n, ll m) {
    if (n<m) return 0;
    return 1ll*f[n]*qpow(f[m],md-2)%md*qpow(f[n-m],md-2)%md;//这里一不小心就会被long long 卡爆
}
int t,n,m,k;

int main(){
    f[0]=1;
    for(int i=1;i<=200000;i++)
        f[i]=f[i-1]*i%md;    

    read(t);//快读相关
    while(t--){
        read(n,m,k);
        for (int i=0; i<n;i++) 
            read(a[i]);//快读相关

        sort(a,a+n);//排序以便枚举
        int p=0;
        ll ans=0;
        for (int i=0;i<n;i++){
            p=(int)(upper_bound(a,a+n,a[i]+k)-a);
            if(p-i>=m) {
                ans+=ght(p-i-1,m-1);
                ans%=md;
            }
        }
        wrti(ans);//快写相关
    }
    flush();//快写相关
    return 0;
}

Easy 版本 就是设组合数的最大最小值之差为 $2$,且每组只查 $3$ 个元素,原理是一样的。

不开龙龙爆零零!!!!


The Only Thing That's Changed is EVERYTHING .