题目描述

给定$n$,要求找到$k$个不同的组合数$\binom{a_i}{b_i}$满足$0≤b_i≤a_i≤n$且所有组合数本质不同。

两个组合数本质不同当且仅当$a_i≠a_j$或$b_i≠b_j$

输入格式

从标准输入读入数据。

第一行两个整数 $n,k$。

输出格式

输出到标准输出。

一行一个整数，代表 $k$ 个组合数的和对 $10^9+7$取模之后的结果；数据保证一定有至少 $k$ 个数可以选。

输入输出样例

input:
2 3
output:
4

说明/提示

对于$100$%的数据，满足$1≤n≤10^6,1≤k≤10^5$

思路

首先有一个显然的结论，若存在一组组合数

$$ \binom{m}{j},\binom{n}{j} \ (m<n) $$
那么有
$$ \binom{m}{j}<\binom{n}{j} $$
那么我们可以把所有的$\binom{n}{i}(0≤i≤n)$放入一个集合维护，每次取出最大的，取$k$次。

那么我们可以维护一个大根堆，存一下二元组$(n,k)$,每次取出$\binom{n}{k}$中最大的，取完后再将$\binom{n-1}{k}$加入大根堆。

但是$n$最多可至$10^6$，通过组合数比较显然不现实，这里采用一种十分巧妙的方法：取对数。
$$ \begin{aligned} log\binom{n}{k}&=log\frac{n!}{k!(n-k)!}\\\ &=log(n!)-log(k!)-log(n-k)!\\\ &=\sum_{i=1}^nlog(i)-\sum_{j=1}^klog(j)-\sum_{p=1}^{n-k}log(n-k) \end{aligned} $$
可以通过预处理前缀和$O(n)$处理出所有的$log$前缀和，然后$O(1)$询问。

总复杂度为$O(n+k\ log\ n)$

代码

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>

const int N = 1e6 + 50,mod = 1e9 + 7;

typedef std::pair<long long,long long> PLL;
typedef std::pair<double,PLL> PDL;

std::priority_queue <PDL,std::vector<PDL>,std::less<PDL> > heap;

long long fac[N],invfac[N];

double sum[N];

namespace wxy{

    inline int C(int n,int m){return n<m?0:(long long)fac[n]*invfac[m]%mod*invfac[n-m]%mod;}

    inline void init(){
        for(int i = 1; i <= 1e6; i++) sum[i] = sum[i - 1] + log(i);
        fac[0]=invfac[0]=invfac[1]=1;
        for(int i=1;i<=1e6;i++)fac[i]=(long long)fac[i-1]*i%mod;
        for(int i=2;i<=1e6;i++)invfac[i]=(long long)(mod-mod/i)*invfac[mod%i]%mod;
        for(int i=2;i<=1e6;i++)invfac[i]=(long long)invfac[i-1]*invfac[i]%mod;
    }

    inline double get(int n,int m){return sum[n] - sum[m] - sum[n - m];}

    inline void insert(int n,int m){
        PDL a;
        a.first = get(n,m);
        a.second.first = n;
        a.second.second = m;
        heap.push(a);
    }

    void main(){
        init();
        int n,k;
        std::cin >> n >> k;
        for (int i = 0;i <= n; i++) insert(n,i);
        long long ans = 0;
        while (k--){
            int n = heap.top().second.first,m = heap.top().second.second;
            ans = (ans % mod + C(n,m) % mod) % mod;
            n--;
            heap.pop();
            if (n >= m) insert(n,m);
        }
        std::cout << ans % mod;
    }

}signed main(){wxy::main();return 0;}