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

da32s1da · 2018-10-01 22:05:18 · 题解

[Code+#4]组合数问题2

求K个不同组合数的最大和。

容易发现n \choose m都比n-1 \choose m要大。

于是一开始可以将所有的n \choose i都丢到一个优先队列中，每次取出最大值x \choose y，然后将x-1 \choose y再丢到优先队列中。重复k次即可。

然而并没有A掉这道题（不然也太水了）。

发现是组合数太大，导致优先队列无法比较。

于是可以考虑对组合数取对数，然后比较，就可以了。

注意\log_2\frac{n!}{m!(n-m)!}=\log_2n!-\log_2m!-\log_2(n-m)!=\sum_{i=1}^n\log_2i-\sum_{i=1}^m\log_2i-\sum_{i=1}^{n-m}\log_2i

做一个\log_2i~的前缀和即可。

#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
const int N=1e6+50;
const int mod=1e9+7;
typedef long long LL;
typedef double D;
typedef pair<int,int> pr;
typedef pair<D,pr> prr;
int n,k;
LL jc[N],ny[N],ans;
D lg[N];
priority_queue <prr>pg;
LL ksm(LL u,LL v){
    LL ret=1;
    for(;v;u=u*u%mod,v>>=1)
    if(v&1)ret=ret*u%mod;
    return ret;
}
void pre(int ha){
    jc[0]=ny[0]=1;
    for(int i=1;i<=ha;i++)jc[i]=jc[i-1]*i%mod;
    ny[ha]=ksm(jc[ha],mod-2);
    for(int i=ha;i>=2;i--)
    ny[i-1]=ny[i]*i%mod;
    for(int i=1;i<=ha;i++)
    lg[i]=lg[i-1]+log(i);
    //预处理阶乘、逆元、对数
}
int main(){
    pre(N-50);
    scanf("%d%d",&n,&k);
    for(int i=0;i<=n;i++)pg.push(prr(lg[n]-lg[n-i]-lg[i],pr(n,i)));
    //初始将C(n,i)丢进去
    for(int i=1;i<=k;i++){
        int x=pg.top().second.first;
        int y=pg.top().second.second;
        pg.pop();
        ans=(ans+jc[x]*ny[y]%mod*ny[x-y]%mod)%mod;
        x--;
        pg.push(prr(lg[x]-lg[x-y]-lg[y],pr(x,y)));
        //每次取出最大的，丢进去新的
    }
    printf("%lld\n",ans);
}