洛谷 P2606 题解

admin 2021-08-22 PM 117℃ 0条

题目链接

分析

题意转化:计算 $1\sim n$ 的排列中,有多少个满足小根堆性质,即 $p_i<\min\{p_{2i},p_{2i+1}\}$。

考虑 DP,设 $dp_i$ 表示 $1\sim i$ 的排列中,有多少个满足小根堆性质。

显然 $p_1=1$,剩下 $i-1$ 个数中,选 $l$ 个作为 $1$ 的左子树,$r$ 个作为 1 的右子树,则:

$$dp_i=dp_l\times dp_r\times\binom{i-1}{l}$$

$l$ 和 $r$ 可以在 DP 时递推得到。

题目保证 $m$ 为质数,但是没有保证 $m>n$,所以求组合数的时候要用 Lucas 定理。阶乘只需要预处理到 $\min\{n,m-1\}$ 即可。

时间复杂度 $O(\min\{n,m\}+n\log_m^n)$。

解决

代码:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1000005;
int n, m, k, fac[N], inv[N], dp[N];
bool inLeft[N];

int C(int x, int y)
{
    if (x < y || y < 0)
        return 0;
    if (x <= k)
        return 1LL * fac[x] * inv[y] % m * inv[x - y] % m;
    return 1LL * C(x / m, y / m) * C(x % m, y % m) % m;
}

int power(int x, int y = m - 2, int p = m)
{
    int ans = 1, base = x;
    while (y)
    {
        if (y & 1)
            ans = 1LL * ans * base % p;
        base = 1LL * base * base % p, y >>= 1;
    }
    return ans;
}

void dfs(int cur)
{
    inLeft[cur] = true;
    if ((cur << 1) <= n)
        dfs(cur << 1);
    if ((cur << 1 | 1) <= n)
        dfs(cur << 1 | 1);
}

int main()
{
    cin >> n >> m;
    k = min(n, m - 1);
    fac[0] = 1;
    for (int i = 1; i <= k; i++)
        fac[i] = 1LL * fac[i - 1] * i % m;
    inv[k] = power(fac[k]);
    for (int i = k - 1; i >= 0; i--)
        inv[i] = 1LL * inv[i + 1] * (i + 1) % m;
    dp[0] = dp[1] = 1;
    if (n >= 2)
        dfs(2);
    for (int i = 2, l = 0, r = 0; i <= n; i++)
    {
        if (inLeft[i])
            l++;
        else
            r++;
        dp[i] = 1LL * dp[l] * dp[r] % m * C(i - 1, l) % m;
    }
    cout << dp[n] << endl;
    return 0;
}

非特殊说明,本博所有文章均为博主原创。

上一篇 洛谷 P1587 题解
下一篇 CF 97E 题解

评论啦~