洛谷 P2606 [ZJOI2010] 排列计数

---

题目传送门

---

前言

ZJ 省十五年前的省选题思路依旧逆天，能通过下标 $\lfloor i/2\rfloor$ 想到二叉堆的也是无敌了 （但应该是我太菜了）。为了削减颓题解的负罪学习这种新颖的 $dp$ 思路，我决定写篇题解。

---

思路

问题转化

如前言所说，题目让我们构造 $p_i>p_{i/2}$ 的序列可以转化为构造一个二叉小根堆。

状态设计

设 $d{p}_u$ 表示以 $u$ 为根节点的子树共有多少种二叉小根堆。

转移方程

假设以 $u$ 为根节点的子树大小为 $si{z}_u$。

因为要满足小根堆性质，所以说 $u$ 的数值必须是所有的 $si{z}_u$ 中最小的那一个。
把最小的那个挑出来之后剩下 $si{z}_u-1$ 个，再从中挑 $si{z}_{2u}$ 个来构造左子树，共有 $C_{si{z}_u-1}^{si{z}_{2u}}$ 种可能，剩下的去构造右子树。

因此有：
$$d{p}_u=d{p}_{2u}\times d{p}_{2u+1}\times C_{si{z}_u-1}^{si{z}_{2u}}$$

至于怎么求 $si{z}_u$，提前 $dfs$ 预处理一下即可。

复杂度

由于求组合数取模时要用到卢卡斯定理，所以时间复杂度为 $O(n\times lo{g}_m(n))$，空间复杂度 $O(n)$。

---

代码

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e6 + 7;ll n, p;
ll siz[maxn];
ll dfs(int u) {siz[u] = 1;if ((u << 1) <= n) siz[u] += dfs(u << 1);if ((u << 1 | 1) <= n) siz[u] += dfs(u << 1 | 1);return siz[u];
}ll fac[maxn], inv[maxn];
ll qpow(ll x,ll y) {ll res = 1;for (; y; y >>= 1, x = x * x % p)if (y & 1) res = res * x % p;return res;
}
void init() {fac[0] = inv[0] = 1;for (ll i = 1; i <= n; ++i) {fac[i] = fac[i - 1] * i % p;inv[i] = qpow(fac[i], p - 2);}
}
ll C(ll x, ll y) {if (x < y) return 0;return fac[x] * inv[x - y] % p * inv[y] % p;
}
ll Lucas(ll x, ll y, ll p) {if (y == 0) return 1;return C(x % p, y % p) * Lucas(x / p, y / p, p) % p;
}ll dp[maxn];
ll DP(int u) {if (u * 2 > n) return 1;if (u * 2 + 1 > n) return 1;
//	DP(u * 2), DP(u * 2 + 1);
//	dp[u] = Lucas(siz[u] - 1, siz[u * 2], p) * dp[u * 2] % p * dp[u * 2 + 1] % p;return Lucas(siz[u] - 1, siz[u * 2], p) * DP(u * 2) % p * DP(u * 2 + 1) % p;
}
int main() {scanf("%lld%lld", &n, &p);dfs(1), init();
//	for (int i = 1; i <= 5; ++i) {
//		for (int j = 1; j <= i; ++j) {
//			printf("C(%d, %d) = %lld\n", i, j, Lucas(i, j, p));
//		}
//	}printf("%lld\n", DP(1));return 0;
}