题目地址：洛谷：【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;
}