[ZJOI2010]排列计数 题解
题目地址:洛谷:【P2606】[ZJOI2010]排列计数 – 洛谷、BZOJ:Problem 2111. — [ZJOI2010]Perm 排列计数
题目描述
称一个1,2,…,N的排列P1,P2…,Pn是Magic的,当且仅当2<=i<=N时,Pi>Pi/2. 计算1,2,…N的排列中有多少是Magic的,答案可能很大,只能输出模P以后的值
输入输出格式
输入格式:
输入文件的第一行包含两个整数 n和p,含义如上所述。
输出格式:
输出文件中仅包含一个整数,表示计算1,2,⋯, ���的排列中, Magic排列的个数模 p的值。
输入输出样例
输入样例#1:
20 23
输出样例#1:
16
说明
100%的数据中,1 ≤N ≤ 10^6, P≤ 10^9,p是一个质数。
题解
发现了一个奇特的性质,如果把这个数组看成是一棵二叉树,节点i对应的左右儿子分别是2i和2i+1,那么这个序列的二叉树是一个小根堆。
我们考虑一个分治的思想,对于一个数集建立完全二叉树的小根堆,一定是取最小元素当堆顶,然后将元素分成左右子树再进行计算,由于左右子树的大小一定比当前数集的大小小,可以使用动态规划来解决这个问题。我们从数集中选出左子树那么多元素还要乘上一个组合系数,即:
dp[i] = \mathrm{C}_{i-1}^l dp[l] dp[r]
由于我们不能O(n^2)地预处理组合数,必须使用Lucas定理来求。划分左右子树的时候,可以先检查左子树是否填满,满了就往右子树填。要判断左子树满没满,我们可以计算出最后一层有n - (2^{\lfloor \log n \rfloor} - 1)这么多节点,判断最后一层满一半没有即可。
代码
// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
register char c = fgc();
while(!isdigit(c)) {
if(c == '-') neg = -1;
c = fgc();
}
while(isdigit(c)) {
res = (res << 1) + (res << 3) + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 1000005;
LL n, p, Log[MAXN], mul[MAXN], inv[MAXN], dp[MAXN];
inline void init() {
Log[2] = 1;
for(int i = 3; i < MAXN; i++) {
Log[i] = Log[i >> 1] + 1;
}
mul[0] = mul[1] = inv[0] = inv[1] = 1;
for(int i = 2; i < MAXN; i++) {
inv[i] = (-(p / i) * inv[p % i] % p + p) % p;
}
for(int i = 2; i < MAXN; i++) {
mul[i] = i * mul[i - 1] % p;
inv[i] = inv[i] * inv[i - 1] % p;
}
}
inline LL lucas(LL n, LL m) {
if(m > n) return 0;
if(n < p && m < p) return mul[n] * inv[n - m] % p * inv[m] % p;
return lucas(n / p, m / p) * lucas(n % p, m % p) % p;
}
int main() {
n = readint(); p = readint();
init();
dp[1] = dp[2] = 1 % p; dp[3] = 2 % p;
int l = 1, r = 1;
for(int i = 4; i <= n; i++) {
if(i - (1 << Log[i]) + 1 <= 1 << (Log[i] - 1)) l++; else r++;
dp[i] = lucas(i - 1, l) * dp[l] % p * dp[r] % p;
}
printf("%lld", dp[n]);
return 0;
}