洛谷P2606《排列计数》

七月 21, 2019 2928

披着数论皮的图论

题目描述

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

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例

1
20 23

输出样例

1
16

说明

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

解析

考虑这么一个事情：

P_i > P_{i / 2} 放到一棵树上是什么？
把 P_i 看作第 i 个点的权值，那么……
第 i 个点的权值比第 i/2 个点的权值要大，也就是第 i 个点的权值要比第 i \times 2 个点的权值要小……
想一想二叉树的表示方法……这好像是一个小根堆？

问题转化为了：求1-n的所有排列中，可以构成一个小根堆的排列的个数

考虑dp
设dp[u]表示以u为根结点分配1~size(u)的小根堆的方案数
转移：MATHJAX-SSR-1349

最终答案就是 dp(1)

代码实现

我开了O2才过。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <cctype>
#include <cstdio>
#include <vector>

const int MAXN = 1e6 + 10;

long long int n, HA, fac[MAXN], inv[MAXN], siz[MAXN], dp[MAXN];
std::vector<int> head[MAXN << 1];

/*
long long int getll() { 
    long long int s = 0, x = 1; 
    char ch = getchar(); 
    while (!isdigit(ch)) { if (ch == '-') x = -1; ch = getchar(); } 
    while (isdigit(ch)) { s = s * x + 1ll * ch - 1ll * '0'; ch = getchar(); } 
    return 1ll * s * x; 
}
void putll(long long int x) { 
    if (x < 0) { putchar('-'); x = -x; } 
    putll(x / 10); putchar(x % 10 + '0'); 
}
*/

long long int fastPow(long long int a, long long int b) {
    if (b == 0) return 1;
    if (b == 1) return a % HA;
    long long int ret = 1;
    while (b) {
        if (b & 1) ret = ret * a % HA;
        a = a * a % HA;
        b >>= 1;
    }
    return ret;
}

long long int C(long long int m, long long int n) {
    // 洛谷上数据水不用 Lucas 定理
    // n! / (m!(n - m)!)
    return fac[n] * inv[m] % HA * inv[n - m] % HA;
}

inline void addEdge(int prev, int next) {
    head[prev].push_back(next);
    head[next].push_back(prev);
}

void DFS(long long int father = 0, long long int root = 1) {
    siz[root] = 1;
    dp[root] = 1;
    for (int i = 0, ss = head[root].size(); i < ss; ++i) {
        int next = head[root][i];
        if (father == next) continue;
        DFS(root, next);
        siz[root] += siz[next];
        dp[root] = 1ll * dp[root] * C(siz[next], siz[root] - 1) % HA * dp[next] % HA;
    }
}

int main() {
    //n = getll(); HA = getll();
    scanf("%lld %lld", &n, &HA);
    fac[0] = 1; inv[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fac[i] = fac[i - 1] * i % HA;
        inv[i] = fastPow(fac[i], HA - 2);
        int lson = (i << 1), rson = (i << 1 | 1);
        if (lson <= n) addEdge(i, lson);
        if (rson <= n) addEdge(i, rson);
    }
    DFS();
    //putll(dp[1] % HA);
    printf("%lld\n", dp[1] % HA);
    return 0;
}