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

题目链接

https://www.luogu.org/problem/P4370

题解

组合数显然有如下性质：

$$C_x^y>C_{x-1}^y$$

于是可以用堆维护当前最大组合数值：先将 \(C_n^0 \ldots C_n^n\) 全部插入堆中，每次取出最大值 \(C_x^y\) 后，将 \(C_{x-1}^y\) 插入堆中，直到取够 \(k\) 元素后停止。

但组合数显然会爆 long long，不能直接比较。

可以考虑将组合数取对数后比较。

$$\log C_x^y=\log \frac{x!}{y!(x-y)!}= \sum_{i=1}^{x} \log i-\sum_{i=1}^y \log i-\sum_{i=1}^{x-y} \log i$$

预处理阶乘，阶乘的逆元，对数前缀和即可。

#include <cmath>
#include <iostream>
#include <queue>
#define MOD 1000000007
using namespace std;
struct node
{
 int x,y;
 double v;
 bool operator<(const node&a)const
 {
  return v<a.v;
 }
};
priority_queue<node> q;
double sum[1000005];
long long f[1000005],inv[1000005];
long long fpow(long long x,int y)
{
 long long ans=1;
 while(y)
 {
  if(y&1)ans=ans*x%MOD;
  x=x*x%MOD;
  y>>=1;
 }
 return ans;
}
double c1(int x,int y)
{
 return sum[x]-sum[y]-sum[x-y];
}
long long c2(int x,int y)
{
 return f[x]*inv[y]%MOD*inv[x-y]%MOD;
}
int main()
{
 int n,k;
 cin>>n>>k;
 f[0]=inv[0]=1;
 for(int i=1;i<=n;i++)
  f[i]=f[i-1]*i%MOD;
 inv[n]=fpow(f[n],MOD-2);
 for(int i=n;i>1;i--)
  inv[i-1]=inv[i]*i%MOD;
 for(int i=1;i<=n;i++)
  sum[i]=sum[i-1]+log(i);
 for(int i=0;i<=n;i++)
  q.push({n,i,c1(n,i)});
 long long ans=0;
 for(int i=1;i<=k;i++)
 {
  int x=q.top().x,y=q.top().y;
  q.pop();
  ans=(ans+c2(x,y))%MOD;
  if(x>y)q.push({x-1,y,c1(x-1,y)});
 }
 cout<<ans<<endl;
 return 0;
}