洛谷 P2606 [ZJOI2010] 排列计数 题解

题目链接

[ZJOI2010] 排列计数 - 洛谷

题解

看到 \(p_i > p_{\lfloor i/2 \rfloor}\) 这个条件，可能一开始不会有什么想法。但是如果我们换种写法, 即: \(p_i<p_{2i} \land p_i<p_{2i+1}\)。这样我们就能很容易看出来，这是小根堆的形式。

现在我们从根节点开始考虑，假设左子树的大小为 \(a\)，右子树的大小为 \(b\)，那么根节点的选择显然只有一种，剩下由其子树内部分配，其中这一步的方案数为 \(C_{a+b}^a\)，即把剩下的数选 \(a\) 个分给左子树，剩下的给右子树。由于每一层的决策都是独立的，所以最后的答案就是这些相乘。

值得注意的是，这题可能存在 \(n>m\) 的情况，即 \(n\) 可能是 \(m\) 的倍数，这种情况下没办法正常的维护逆元，所以需要用到 \(Lucas\)定理。

代码

#include <bits/stdc++.h>

using i64 = long long;

struct Lucas
{
	int p;
	std::vector<i64> fac, inv;

	Lucas() {}
	Lucas(int n)
	{
		init(n);
	}

	void init(int n)
	{
		p = n;
		fac.assign(n, 1);
		inv.assign(n, 1);

		for(int i = 1; i < n; i++) fac[i] = fac[i - 1] * i % n;

		for(int i = 2; i < n; i++) inv[i] = (n - n / i) * inv[n % i] % n;
		for(int i = 2; i < n; i++) inv[i] = inv[i] * inv[i - 1] % n;
	}

	i64 binom(int n, int m)
	{
		if(m > n || m < 0) return 0;
		return fac[n] * inv[m] % p * inv[n - m] % p;
	}

	i64 cacl(int n, int m)
	{
		i64 ans = 1;
		while(n || m)
		{
			ans = ans * binom(n % p, m % p) % p;
			n /= p, m /= p;
		}

		return ans;
	}
};

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n, P; std::cin >> n >> P;

	Lucas comb;
	if(n >= P) comb.init(P);

	i64 ans = 1;

	std::vector<i64> fac(n + 1, 1), inv(n + 1, 1);
	for(int i = 2; i <= n; i++) fac[i] = fac[i - 1] * i % P;
	for(int i = 2; i <= n; i++) inv[i] = (P - P / i) * inv[P % i] % P;
	for(int i = 2; i <= n; i++) inv[i] = inv[i] * inv[i - 1] % P;

	auto C = [&](int n, int m) -> i64
	{
		return fac[n] * inv[m] % P * inv[n - m] % P;
	};

	auto dfs = [&](auto dfs, int p) -> int
	{
		if(p > n) return 0;
		int a = dfs(dfs, p << 1);
		int b = dfs(dfs, p << 1 | 1);

		if(n < P) ans = ans * C(a + b, a) % P;
		else ans = ans * comb.cacl(a + b, a) % P;
		return a + b + 1;
	};	
	dfs(dfs, 1);

	std::cout << ans << "\n";

	return 0;
}