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

​​​​

其实也不难想，\((^i_j)>(^{i+1}_j)\)，那这道题就做完了，用优先队列维护 \((^{...}_j)\) 即可。

不过这里组合数直接比较会裂开，可以取对数比较 √。

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#define mr make_pair
#define pr pair <int, int>
#define LL long long
#define uint unsigned int
using namespace std;
#define Debug(x) cerr << #x << ' ' << x
#define hh cerr << endl
const int Mod = 1e9 + 7, MAXN = 1e6 + 5;
int n, k;
struct Node {
double V;
int X, Y;
bool operator < (const Node P) const { return V < P.V; }
Node() {}
Node(int x, int y, double v) { X = x; Y = y; V = v; }
};
double val[MAXN];
LL jc[MAXN], inv[MAXN], res;
priority_queue <Node> que;
double Getval(int x, int y) { return val[y] - val[x] - val[y - x]; }
LL Getans(int x, int y) { return jc[y] * inv[x] % Mod * inv[y - x] % Mod; }
LL Qpow(LL x, int y) { LL ans = 1; for(; y; y >>= 1) { if(y & 1) ans = ans * x % Mod; x = x * x % Mod; } return ans; }
int main() {
scanf("%d%d", &n, &k); jc[0] = inv[0] = 1; val[0] = 0;
for(int i = 1; i <= n; i ++) jc[i] = jc[i - 1] * i % Mod, val[i] = val[i - 1] + log2(i);
inv[n] = Qpow(jc[n], Mod - 2); for(int i = n - 1; i >= 0; i --) inv[i] = inv[i + 1] * (i + 1) % Mod;
for(int i = 0; i <= n; i ++) que.push(Node(i, n, Getval(i, n)));
for(int i = 1; i <= k; i ++) {
Node t = que.top(); que.pop(); res = (res + Getans(t.X, t.Y)) % Mod;
t.Y --;
if(t.Y >= t.X) t.V = Getval(t.X, t.Y), que.push(t);
  }
printf("%lld", res);
return 0;
}