「Bzoj 2111」「ZJOI2010」排列计数 (树形计数DP)

发表于 | 分类于 | | + s

BZOJ 2111
题意：称一个$1,2,…,N​$的排列$P_1,P_2…,P_n​$是$\text{Magic}​$的，当且仅当$2 \leq i \leq N​$时，$P_i > P_{\frac i2}​$. 计算$1，2，…N​$的排列中有多少是$\text{Magic}​$的，答案可能很大，只能输出模$P​$以后的值

容易转化为即求小根堆的方案数。
那么我们可以用树形DP方法来做，设$dp(i)$为以$i$为根($P$的下标$i$)的方案数。
那么这个树的左右子树大小是定的，那么就有
$$
dp(i)=C^{s-1}_{n-i} dp(ls) \cdot dp(rs)
$$
其中$ls, rs$为左右子树大小，$s$为$i$子树大小
即$i$子树候选集合大小为$n-i$，从候选集合选出$s-1$个来当$i$的子树，然后分别乘上左儿子右儿子的方案即可。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MAXN = 2000000 + 5;

    LL n, p, dp[MAXN], jc[MAXN], jc_inv[MAXN], s[MAXN];

    LL ksm(LL a, LL b) {
        LL ans = 1, bs = a;
        while (b) {
            if (b & 1) ans = ans * bs % p;
            bs = bs * bs % p;
            b >>= 1;
        }
        return ans;
    }
    LL C(LL n, LL m) {
        if (m > n) return 0;
        return jc[n] * jc_inv[n - m] % p * jc_inv[m] % p;
    }
    LL lucas(LL n, LL m) {
        if (m == 0) return 1;
        return lucas(n / p, m / p) * C(n % p, m % p) % p;
    }
    void dfs_siz(LL u) {
        if (u > n) return ;
        s[u] = 1;
        dfs_siz(u * 2), dfs_siz(u * 2 + 1);
        s[u] += s[u * 2] + s[u * 2 + 1];
    }
    void dfs(LL u) {
        if (u * 2 > n) return dp[u] = 1, void();
        dfs(u * 2), dfs(u * 2 + 1);
        LL t1 = dp[u * 2], t2 = dp[u * 2 + 1];
        if (t1 == 0) t1 = 1;
        if (t2 == 0) t2 = 1;
        dp[u] = lucas(s[u] - 1, s[u * 2]) * t1 % p * t2 % p;
    }

    void clean() {
    }
    int solve() {

        clean();
        cin >> n >> p;
        jc[0] = jc_inv[0] = 1;
        for (LL i = 1; i <= 1000000; ++i) jc[i] = jc[i - 1] * i % p, jc_inv[i] = ksm(jc[i], p - 2);
        dfs_siz(1);
        dfs(1);
        printf("%lld\n", dp[1]);

        return 0;
    } 
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------