Luogu P2606 [ZJOI2010]排列计数 题解
题目描述
称一个 \(1 \sim n\) 的排列 \(p_1,p_2, \dots ,p_n\) 是 Magic 的，当且仅当
\[\forall i \in [2,n],p_i > p_{\lfloor i/2 \rfloor}. \]计算 \(1 \sim n\) 的排列中有多少是 Magic 的，答案可能很大，只需输出模 \(m\) 以后的值。
思路
把题目中给的条件转化一下，变成：对于每一个 \(i\)，满足 \(p_i<p_{2i}\) 且 \(p_i<p_{2i+1}\)。
发现 \(2i\) 和 \(2i+1\) 即为二叉树上节点 \(i\) 的两个儿子，上述性质符合小根堆的性质。
设 \(s_i\) 表示以 \(i\) 为根的子树大小，\(f_i\) 表示用 \(1,2,\dots,s_i\) 填满以 \(i\) 为根的子树且满足上述性质的方案数。显然，用 \(1,2,\dots,s_i\) 和 \(2,3,\dots,s_i+1\) 填的方案是等效的，即方案数与 \(i\) 本身的值无关，而与 \(s_i\) 的大小有关。
考虑在二叉树上 DP：从叶子到根，先由子树的大小算出 \(s_i\)，然后再由子树的方案数和 \(s_i\)算出 \(f_i\)。设两个子树分别是 \(l\) 和 \(r\)，则需要从 \(s_i\) 个数中选出 \(s_{l}\) 和 \(s_{r}\) 个分别给两个子树，方案数为 \(\dbinom{s_i-1}{s_{l}}\)。于是，根据分步乘法原理，转移方程为
\[f_i=f_{l}\times f_{r}\times\dbinom{s_i-1}{s_{l}}. \]最后的答案为 \(f_1\)。
代码
- 由于叶子节点没有子树，\(f\) 数组的初值须全部设为 \(1\)，不然会输出
0； - 并且，\(s\) 数组和 \(f\) 数组需要开大一倍，不然会 RE；
- 由于模数很小，可以用 Lucas 定理求组合数。
- （预处理出阶乘比直接算要快 0.4 秒左右，不过都能过）
- （
fill函数是 stl 库中用于给数组内所有元素赋值的函数，与memset不同） （十年 OI 一场空，不开long long见祖宗）
（快速幂模板省略）
#include <iostream>
#include <algorithm>
#define f(x, y, z) for (int x = (y); (x) <= (z); ++(x))
#define g(x, y, z) for (int x = (y); (x) >= (z); --(x))
#define il inline
#define ls (i << 1)
#define rs (i << 1 | 1)
#define int ll
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int n, p, s[N << 1], f[N << 1];
int fac[N];
il void Init(int p) {
fac[0] = fac[1] = 1;
f(i, 2, n) fac[i] = fac[i - 1] * i % p;
}
il int ksm(int a, int x, int p) { ... }
il int C(int n, int m, int p) {
// int a = 1, b = 1;
// f(i, n - m + 1, n) a = a * i % p;
// f(i, 2, m) b = b * i % p;
// return a * ksm(b, p - 2, p) % p;
return fac[n] * ksm(fac[m] * fac[n - m] % p, p - 2, p) % p;
}
int Lucas(int n, int m, int p) {
if (!m) return 1;
return C(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
}
signed main() {
cin >> n >> p;
Init(p);
fill(f, f + (N << 1), 1);
g(i, n, 1) {
s[i] = s[ls] + s[rs] + 1;
f[i] = f[ls] * f[rs] % p * Lucas(s[i] - 1, s[ls], p) % p;
}
cout << f[1] << '\n';
return 0;
}