题解 [ZJOI2010]排列计数

好题。

% 你赛考到了不会摆烂，后来发现原来有向下取整，题面没有。。。（

就算有我也做不出来啦 qAq

首先我们会发现这个长得就是小根堆，答案就变成了小根堆的计数。

首先最小的数字肯定放在根的位置。我们令 \(f_i\) 为有 \(i\) 个数字组成的小根堆形态数量。显然小根堆左儿子和右儿子的数量是固定的，令左儿子 \(l\) 个右儿子 \(r\) 个，则显然有 \(f_i = C_{i - 1}^l\times f_l \times f_r\)。

组合数用 Lucas 求。

#include <iostream>

#define MAXN 1000000

using namespace std;

int n, m, Mod;

int qpow(int n, int m) {

	int res = 1, bas = n;

	while(m) {

		if(m & 1) res = res * bas % Mod;

		bas = bas * bas % Mod;

		m >>= 1;

	}

	return res;

}

int fac[MAXN + 10];

void pre() {

	fac[0] = 1, fac[1] = 1;

	for(int p = 2; p <= MAXN; p++) fac[p] = fac[p - 1] * p % Mod;

}

int inv(int x) {

	return qpow(x, Mod - 2);

}

int C(int n, int m) {//C_n^m

	if(m > n) return 0;

	return fac[n] * inv(fac[m]) % Mod * inv(fac[n - m]) % Mod;

}

int Lucas(int n, int m) {//C_n^m

	if(!m) return 1;

	else return Lucas(n / Mod, m / Mod) * C(n % Mod, m % Mod) % Mod;

}

int f[MAXN + 10];

int main() {

	cin >> n >> Mod;

	pre();

	f[1] = 1, f[2] = 1, f[3] = 2;

	int l = 1, r = 1, lim = 3;

	for(int p = 4; p <= n; p++) {

		if(l < lim) l++;

		else r++;

		if(l == r) lim = (lim + 1) * 2 - 1;

		f[p] = Lucas(p - 1, l) * f[l] % Mod * f[r] % Mod;

	}

	cout << f[n] << endl;

}

巴特西

题解 [ZJOI2010]排列计数

最新文章

热门文章