【题解】堆

请注意,本文编写于 94 天前,最后修改于 94 天前,其中某些信息可能已经过时。

Problem

求有多少个点权为 $1$ 到 $n$ 且互不相同的 $n$ 个点的二叉堆

$subtask1:n\leq10^6$
$subtask2:n\leq10^9$

Thought

比较 naive 的想法是设 $f[x]$ 为节点 $x$ 作为根的答案

显然 $key[x]$ 必然是比其子树中节点都小,并且左右子树间大小互不影响

那么可以推得: $f[x]={siz[L]+siz[R]\choose siz[L]}*f[L]*f[R]$

有了这个式子已经可以做到 $O(n)$ 解决原问题,完成 $subtask1$

但是当 $n\leq10^9$ 时,连组合数都无法进行计算,如何解决?

考虑将原式拆开:

$$ f[x]={siz[L]+siz[R]\choose siz[L]}*f[L]*f[R]\\ f[x]=\frac{(siz[L]+siz[R])!}{siz[L]!siz[R]!}*f[L]*f[R]\\ f[x]=\frac{1}{siz[x]}*\frac{siz[x]!}{siz[L]!siz[R]!}*f[L]*f[R] $$

如果我们将 $f[L],f[R]$ 同样用这样的形式递归代入,最后会发现:

$$ f[1]=\frac{n!}{\prod_{i=1}^{n} siz[i]} $$

对于 $\prod_{i=1}^{n} siz[i]$ ,由于二叉堆的一些比较妙的性质,可以在 $\log n$ 的时间内得到答案

首先 $DP$ 算出 $g(x)$ 表示深度为 $x$ 的满二叉树的 $\prod_{i=1}^{2^x-1} siz[i]$

边界条件 $g(1)=1$ ,方程 $g(x)=g(x-1)^2*(2^x-1)$

由于对于一个二叉堆来说,首先它是一个完全二叉树,那么其每一层必定有一个子树为满二叉树,然后递归另一子树即可

接下来求 $n!$
真是个 $**$ 玩意儿

法一:

考虑构造多项式 $F(x)=x(x+1)(x+2)\cdots(x+\sqrt{n}-1)$
求出 $F(1)*F(\sqrt{n})*F(2\sqrt{n})\cdots$ 即为 $n!$

可以使用多点求值,时间复杂度 $O(\sqrt{n}\log^2\sqrt{n})$

法二:

分段打表

Code

分段打表真香

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll FAC[10010] = {};
const int mod = 1000000007;

ll read() {
    ll ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}

int n, g[40];

int qpow(int a, int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ans;
}

void prepare() {
    g[0] = g[1] = 1;
    for(int i = 2; i <= 30; ++ i)
        g[i] = 1ll * g[i - 1] * g[i - 1] % mod * ((qpow(2, i) - 1 + mod) % mod) % mod;
}
int cal(int x) {
    if(x == 0) return 1;
    int ans = x, now = x, d = 0;
    for(int i = 1; now >= 1 << (i - 1); ++ i) {
        ++ d;
        now -= 1 << (i - 1);
    }
    if(now >= 1 << (d - 1)) {
    freopen("heap.in", "r", stdin);
    freopen("heap.out", "w", stdout);
        ans = 1ll * ans * g[d] % mod;
        ans = 1ll * ans * cal(x - (1 << d)) % mod;
    }
    else {
        ans = 1ll * ans * g[d - 1] % mod;
        ans = 1ll * ans * cal(x - (1 << (d - 1))) % mod;
    }
    return ans;
}

int main() {
    prepare(); 
    n = read();
    int c = qpow(cal(n), mod - 2);
    c = 1ll * c * FAC[n / 100000] % mod;
    int last = n - n % 100000;
    for(int i = 1; i <= n % 100000; ++ i)
        c = 1ll * c * (last + i) % mod;
    printf("%d\n", c);
    return 0;
}
Comments

添加新评论