Rockdu's Blog

题目描述

称一个1,2,...,N的排列P1,P2...,Pn是Magic的，当且仅当2<=i<=N时，Pi>Pi/2. 计算1，2，...N的排列中有多少是Magic的，答案可能很大，只能输出模P以后的值

输入输出格式

输入格式：

输入文件的第一行包含两个整数 n和p，含义如上所述。

输出格式：

输出文件中仅包含一个整数，表示计算1,2,⋯, ���的排列中， Magic排列的个数模 p的值。

输入输出样例

20 23

16

说明

100%的数据中，1 ≤N ≤ 10^6, P≤ 10^9，p是一个质数。

挺有趣的一道题，玩着玩着发现这题是在统计小根堆的个数。

那么就简单了，对于一个n个点的小根堆来说，它的形态是固定的，并且根的左右子树都是一个小根堆。

这样我们每一次去找根的左右子树分别是几个点的堆，选一些数放到左子树去，剩下的到右子树去就好了。所以我们预处理一个组合数，乘法原理乘一下方案就行了。

要注意左右子树大小不是很好直接计算，建议实时模拟维护。

#include<cstdio>
#define LL long long
using namespace std;
const int maxn = 1e6 + 5;
int n, dp[maxn], p, pos, siz;
int step[maxn], inv[maxn];

LL fpow(LL a, int b) {
    LL ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % p;
        a = a * a % p, b >>= 1;
    }
    return ans;
}

void pre(int n) {
    step[0] = inv[0] = 1;
    for(register int i = 1; i <= n; ++i)
        step[i] = 1ll * step[i - 1] * i % p;
    inv[n] = fpow(step[n], p - 2);
    for(register int i = n - 1; i >= 1; --i) 
        inv[i] = 1ll * inv[i + 1] * (i + 1) % p;
}

LL C(int n, int m) {
    return (1ll * step[n] * inv[n - m] % p) * inv[m] % p;
}

int main() {
    scanf("%d%d", &n, &p);
    pre(n), dp[1] = dp[0] = 1, siz = pos = 1;
    int l = 0, r = 0;
    for(register int i = 2; i <= n; ++i) {
        if((siz << 1) + 1 < i) 
            pos = pos << 1, siz = ((pos << 1) - 1);
        if(i - siz <= pos) ++l;
        else ++r;
        dp[i] = (1ll * dp[l] * dp[r] % p) * C(i - 1, l) % p;
    }
    printf("%d", dp[n]);
    return 0;
}