\(\mathcal{Description}\)

给定 \(n,k\)，求 \(0\le b\le a\le n\) 的 \(\binom{a}{b}\) 的前 \(k\) 大。

\(n\le10^6\)，\(k\le10^5\)。

\(\mathcal{Solution}\)

注意到 \(\binom{a}{b}<\binom{a+1}{b}\)，所以把 \(\binom{n}i\) 塞进堆里，取走堆顶的 \(\binom{a}{b}\) 时顺手把 \(\binom{a-1}b\) 入堆就好。

但组合数直接算会爆精度，取对数就能实现比较了。

\(\mathcal{Code}\)

#include <cmath>

#include <queue>

#include <cstdio>

typedef std::pair<int, int> pii;

const int MAXN = 1e6, MOD = 1e9 + 7;

int n, K, nfac[MAXN + 5], ifac[MAXN + 5];

double lfac[MAXN + 5];

inline double combl ( const int n, const int m ) {

	return lfac[n] - lfac[m] - lfac[n - m];

}

inline int combn ( const int n, const int m ) {

	return 1ll * nfac[n] * ifac[m] % MOD * ifac[n - m] % MOD;

}

inline int qkpow ( int a, int b, const int p = MOD ) {

	int ret = 1;

	for ( ; b; a = 1ll * a * a % p, b >>= 1 ) ret = 1ll * ret * ( b & 1 ? a : 1 ) % p;

	return ret;

}

struct cmp {

	inline bool operator () ( const pii a, const pii b ) {

		return combl ( a.first, a.second ) < combl ( b.first, b.second );

	}

};

std::priority_queue<pii, std::vector<pii>, cmp> heap;

int main () {

	scanf ( "%d %d", &n, &K );

	nfac[0] = nfac[1] = 1;

	for ( int i = 2; i <= n; ++ i ) {

		lfac[i] = lfac[i - 1] + log2 ( i );

		nfac[i] = 1ll * i * nfac[i - 1] % MOD;

	}

	ifac[n] = qkpow ( nfac[n], MOD - 2 );

	for ( int i = n - 1; ~ i; -- i ) ifac[i] = ( i + 1ll ) * ifac[i + 1] % MOD;

	for ( int i = 0; i <= n; ++ i ) heap.push ( { n, i } );

	int ans = 0;

	while ( K -- ) {

		pii t = heap.top (); heap.pop ();

		ans = ( ans + combn ( t.first, t.second ) ) % MOD;

		if ( t.first && t.first ^ t.second ) heap.push ( { t.first - 1, t.second } );

	}

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

	return 0;

}

巴特西

Solution -「Code+#4」「洛谷 P4370」组合数问题 2

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章