题解 P4370 【[Code+#4]组合数问题2】

· · 题解

这道题是zhx出的呢~~

题意很简单，从可选元素总数小于n的所有组合数中选出最大的k个。

我们首先面对数据点编程，只选一个的话，最大的绝对是C^{\frac{n}{2}}_n

那么自然而然产生一个问题，其次大的组合数是什么呢？我们无非只有三种选择

C^{\frac{n}{2}}_{n-1}$ 与$C^{\frac{n}{2}+1}_{n}$ 以及$C^{\frac{n}{2}-1}_{n}

这提示了我们，我们可以从C^{\frac{n}{2}}_n 扩展开来，直到选择所有的k个，这个扩展的过程可以我们拿堆去维护。

但是这里会出现另一个结论，就是

C^m_n>C^m_{n-1}

这是显而易见的。这说明什么呢，如果我的C^{\frac{n}{2}+1}_{n}还没有被选，我是绝对不可能选到C^{\frac{n}{2}+1}_{n-1}的。

有了这个结论，我们就可以先把所有C^i_n(0\leq i\leq n)放到堆里面，然后每一次扩展只需要向上扩展，就是从C^i_n扩展到C^i_{n-1}

这个时候我们又会遇到一个问题，如何去比较组合数的大小呢，或者说我们堆的排序函数怎么写呢？只需要用到一个简单的技巧。

蒟蒻曾经做过一道zhx的题是取对数比较大小，在这道题里面可以使用。对数函数是有严格单调性的，可以把很大的数字映射到一个小到我们可以比较的值。

对于一个组合数，对数操作就是

lg C^m_n=lg(\frac{!n}{!m!(n-m)})=lg!n-lg!m-lg!(n-m) =\sum^n_{i=1}lg i-\sum^m_{i=1}lg i-\sum^{n-m}_{i=1}lg i

我们只需要预处理出来对数函数的前缀和就可以。

完整代码

#include<bits/stdc++.h>
#include<queue>
#define ri register int
#define ll long long
using namespace std;
ll mod=1e9+7;
ll jc[1000100],inv[1000100];
double    lg[1000100];
struct Num;
struct Num{
    int a,b;                // 表示b里面选a个 
    ll w;                   // 表示取模后的组合数数值
    double l;               // 表示组合数的log值
    Num(int p,int q)        //初始化一个组合数 
    {
        this->a=p;
        this->b=q;
        this->l=lg[b]-lg[a]-lg[b-a];
        this->w=((jc[b]*inv[a])%mod)*inv[b-a]%mod;
    }
    bool operator < (const Num &r) const    //通过比较对数大小来比较组合数大小 
    {
        return l<r.l;
    }
};
int n,k;
ll ans;
priority_queue <Num> q;
int main()
{
    jc[0]=jc[1]=inv[0]=inv[1]=1;                                //初始化 
    for(ri i=2;i<=1000009;i++)  inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(ri i=1;i<=1000009;i++)  inv[i]=inv[i-1]*inv[i]%mod;
    for(ri i=1;i<=1000009;i++)  jc[i]=jc[i-1]*i%mod;
    for(ri i=1;i<=1000009;i++)  lg[i]=lg[i-1]+log(i);
    scanf("%d%d",&n,&k);
    for(ri i=0;i<=n;i++)
    q.push(Num(i,n));
    while(k--)                                                  //扩展 
    {
        Num tmp=q.top();
        q.pop(); 
        ans=(ans+tmp.w)%mod;
        q.push(Num(tmp.a,tmp.b-1));
    }
    printf("%lld",ans);
}