组合数问题2

C++(g++ 7.5.0) 解法, 执行用时: 88ms, 内存消耗: 22140K, 提交时间: 2023-02-23 01:08:26

// https://ac.nowcoder.com/acm/problem/15476
#include <bits/stdc++.h>

int read() {
    int x = 0, f = 1, c = getchar();
    for (; !isdigit(c); c = getchar())
        if (c == '-') f = -1;
    for (; isdigit(c); x = x * 10 + c - '0', c = getchar())
        ;
    return x * f;
}

using ll = long long;
const int N = 1000010, mod = 1000000007;
int n, k, fac[N], inv[N], ifc[N];
double lfc[N];
ll ans;

struct Binom {
    Binom(int _n, int _r)
        : n(_n), r(_r), length(lfc[_n] - lfc[_r] - lfc[_n - _r]) {}
    Binom(int _n, int _r, int _l) : n(_n), r(_r), length(_l) {}
    int n, r;
    double length;
    bool operator<(const Binom &binom) const { return length < binom.length; }
    int val() {
        if (n < r || r < 0) return 0;
        return 1ll * fac[n] * ifc[r] % mod * ifc[n - r] % mod;
    }
};

std::priority_queue<Binom> pq;

int main() {
    n = read(), k = read();
    fac[0] = fac[1] = inv[0] = inv[1] = ifc[0] = ifc[1] = 1;
    for (int i = 2; i < N - 10; i++) {
        fac[i] = 1ll * fac[i - 1] * i % mod;
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
        ifc[i] = 1ll * ifc[i - 1] * inv[i] % mod;
        lfc[i] = lfc[i - 1] + std::log(i);
    }

    for (int i = n; ~i && (int)pq.size() < k; i--) {
        if (i % 2 == 0) {
            pq.emplace(i, i / 2);
        } else {
            pq.emplace(i, i / 2);
            pq.emplace(i, i / 2 + 1);
        }
    }

    while (k--) {
        Binom binom = pq.top();
        auto [_, r, l] = binom;
        pq.pop();

        ans = (ans + binom.val()) % mod;
        if (r * 2 <= _) pq.emplace(_, std::max(0, r - 1));
        if (r * 2 >= _) pq.emplace(_, r + 1);
    }

    printf("%lld\n", ans);

    return 0;
}

C++14(g++5.4) 解法, 执行用时: 133ms, 内存消耗: 40540K, 提交时间: 2020-02-27 17:52:31

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int>p;
typedef pair<double,p>P;
typedef long long ll;
const ll mod=1e9+7;
int n,k;
double lg[1000010];
ll A[1000010],F[1000010];
ll qpow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
int main()
{
    ll jg=0;
    A[0]=F[0]=1;
    for(int i=1; i<=1000000; i++)
        A[i]=A[i-1]*i%mod;
    F[1000000]=qpow(A[1000000],mod-2);
    for(int i=1000000; i>=2; i--)
        F[i-1]=F[i]*i%mod;
    for(int i=1; i<=1000000; i++)
        lg[i]=lg[i-1]+log(i);
    scanf("%d%d",&n,&k);
    priority_queue<P>Q;
    for(int i=0; i<=n; i++)
        Q.push(P(lg[n]-lg[n-i]-lg[i],p(n,i)));
    for(int i=0; i<k; i++)
    {
        int x=Q.top().second.first;
        int y=Q.top().second.second;
        Q.pop();
        jg=(jg+A[x]*F[y]%mod*F[x-y]%mod)%mod;
        x--;
        Q.push(P(lg[x]-lg[x-y]-lg[y],p(x,y)));
    }
    printf("%lld\n",jg);
    return 0;
}

C++(clang++11) 解法, 执行用时: 126ms, 内存消耗: 40412K, 提交时间: 2020-11-20 08:58:11

//组后的结果应该是杨辉三角形中间的部分的元素，直接求大小越界，通过优先队列和对数来求 lgc(n,m) =lgn!-lgm!-lg(n-m)!
//最后一行入优先队列 ，出队列后每个元素对应上面的元素入队列 
//这样最多有2*k个元素入对了 
#include <bits/stdc++.h>
const int N=1e6+10;
using namespace std;
typedef pair<int,int>pii;
typedef pair<double,pii>pdii;//cnm,n,m
typedef long long ll;
const ll mod=1e9+7;
int n,k;
double lg[N];
ll A[N],F[N];
ll qpow(ll a,ll b) {
	ll ans=1;
	while(b) {
		if(b&1)
			ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
ll C(ll a,ll b){
	return A[a]*F[b]%mod*F[a-b]%mod;
} 
int main() {
	ll ans=0;
	A[0]=F[0]=1;
	for(int i=1; i<N; i++)
		A[i]=A[i-1]*i%mod;
	F[N-1]=qpow(A[N-1],mod-2);
	for(int i=N-1; i>=2; i--)
		F[i-1]=F[i]*i%mod;
	for(int i=1; i<N; i++)
		lg[i]=lg[i-1]+log(i);
	scanf("%d%d",&n,&k);
	priority_queue<pdii>Q;
	for(int i=0; i<=n; i++)
		Q.push(pdii(lg[n]-lg[n-i]-lg[i],pii(n,i)));
	for(int i=0; i<k; i++) {
		int x=Q.top().second.first;
		int y=Q.top().second.second;
		Q.pop();
		ans=(ans+C(x,y))%mod;
		x--;
		Q.push(pdii(lg[x]-lg[x-y]-lg[y],pii(x,y)));
	}
	printf("%lld\n",ans);
	return 0;
}

详情