题目难度

个人觉得有一点难。

推荐理由

考察组合数的性质。

题目知识点

组合数，优先队列

题意

给出 ，求 （即所有组合数）的前 大之和，对 取模。

分析

首先由于 ，因此对于同一个 ， 越大组合数肯定越大。
再来看对于同一个 ，根据高中学的知识，组合数是先递增后递减的，而且有对称性。
这样，对于同一行，我们肯定是从中间往两端扩散的。
于是乎，我们可以搞一个优先队列，先把每一行中间的入队，取满 个就停止。然后每次取当前最大值，再往两边扩散。
如图：
图片说明

红色的是一开始入队的数，偶数行就取最中间的数，奇数行就取中间两个数。
那么我们每次只需要找到一个最大数，如果他是往左边扩散的，就继续往左边扩散；如果是往右边扩散的，就继续往右边扩散。
现在的问题就在于如何比较这么大的组合数，总不能比较取模后的吧。
于是操作来了！！！！！
取对数！！！！
记 。
那么 ，优先队列里存这个就行了！！
大概思路就是这样，具体细节可以看看代码，代码写得比较清楚。
最后分析一下复杂度，由于每次取出一个组合数，只会新加入最多两个组合数。
所以最终加入队列的组合数不超过 个，于是复杂度为 。

代码如下

#include <bits/stdc++.h>
#define N 1000005
using namespace std;
const int mod = 1e9 + 7;
typedef long long LL;
typedef unsigned long long uLL;
LL z = 1;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
int ksm(int a, int b, int p){
    int s = 1;
    while(b){
        if(b & 1) s = z * s * a % p;
        a = z * a * a % p;
        b >>= 1;
    }
    return s;
}
int fac[N], inv[N];
double s[N];
struct node{
    int n, m;
    double s;
    bool operator < (const node & A) const{
        return s < A.s;
    }
};
priority_queue<node> q;
int ans;
double sum;
int C(int n, int m){
    return z * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main(){
    int i, j, k, n, m;
    node t;
    n = read(); k = read();
    for(fac[0] = i = 1; i <= n; i++) fac[i] = z * fac[i - 1] * i % mod, s[i] = s[i - 1] + log(i);//取对数 
    inv[n] = ksm(fac[n], mod - 2, mod);
    for(i = n - 1; i >= 0; i--) inv[i] = z * inv[i + 1] * (i + 1) % mod;
    for(i = n; i >= 0; i--){
        if(i % 2 == 0) q.push(node{i, i / 2, s[i] - s[i / 2] - s[i - i / 2]});//偶数行 
        else{//奇数行 
            q.push(node{i, i / 2, s[i] - s[i / 2] - s[i - i / 2]});
            q.push(node{i, i / 2, s[i] - s[i / 2] - s[i - i / 2]});
        }
        if(q.size() >= k) break;
    }
    while(k--){
        t = q.top(); q.pop();
        n = t.n, m = t.m;
        ans = (ans + C(n, m)) % mod;
        if(m * 2 == n){//中间的往两边扩散 
            sum = s[n] - s[m - 1] - s[n - (m - 1)];
            q.push(node{n, m - 1, sum});
            q.push(node{n, m + 1, sum});
        }
        else{
            if(m * 2 < n){//往左边扩散 
                sum = s[n] - s[m - 1] - s[n - (m - 1)];
                q.push(node{n, m - 1, sum});
            }
            else{//往右边扩散 
                sum = s[n] - s[m + 1] - s[n - (m + 1)];
                q.push(node{n, m + 1, sum});
            }
        }
    }
    printf("%d", ans);
    return 0;
}