看到这个在 $(10^6)^2$ 量级个组合数里面选出 $10^5$ 个最大的， 这种形式让我们想到一个很经典的东西。

把待选的组合数划分成若干组， 每组内部元素单调， 初始时在一个大根堆里存放每组最大的元素，在取出堆顶后， 将堆顶元素所属的组的下一个元素加入堆，这样就可以做到 $O(n \log n)$。

接下来我们画一个杨辉三角看一看：

1
1 1
1 2  1
1 3  3  1
1 4  6  4 1
1 5 10 10 5 1
....

显然这个东西的每一列是单调的。

所以我们考虑把每一列最底下的元素扔进堆里，每次取出来之后拿出他上面的元素， 这样显然可以得到最优解。

但是发现这些组合数是非常大的，达到了 $(10^6)!$ 的量级，肯定是存不下的。

经过这些的启发，我们想到对组合数取对数。

这样就可以存下了。

哈哈哈，我会了。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
int T,n,k;
const int mod=1e9+7,N=1e6+7;
double lf[1001000];
int fac[1001000],inv[1001000];
priority_queue<pair<double,pair<int,int> > > pq;
int qpow(int a,int b){
	int r=1;
	while(b){
		if(b&1) r=r*a%mod;
		a=a*a%mod,b>>=1;
	}
	return r;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	fac[0]=inv[0]=1;
	for(int i=1;i<=N;i++){
		lf[i]=lf[i-1]+log2(i);
		fac[i]=fac[i-1]*i%mod;
	}
	inv[N]=qpow(fac[N],mod-2);
	for(int i=N-1;i>=1;i--){
		inv[i]=inv[i+1]*(i+1)%mod;
	}
	cin>>n>>k;
	for(int i=0;i<=n;i++){
		pq.push({lf[n]-lf[i]-lf[n-i],{n,i}});
	}
	int ans=0;
	while(k--){
		int a=pq.top().se.fi,b=pq.top().se.se;
		pq.pop();
		ans=(ans+fac[a]*inv[b]%mod*inv[a-b]%mod)%mod;
		if(a>b) pq.push({lf[a-1]-lf[b]-lf[a-1-b],{a-1,b}});
	}
	cout<<ans<<'\n';
	return 0;
}