[ZJOI2010] 排列计数（dp + 组合数）

luogu-P2606

我们对 i − ⌊ i 2 ⌋ i-lfloorfrac i2rfloor i−⌊2i​⌋ 远没有 i − 2 ∗ i , 2 ∗ i + 1 i-2*i,2*i+1 i−2∗i,2∗i+1 敏感，这其实就是个二叉树，而且是个小根堆。

每个点的值都小于左右儿子的值（如果有左右儿子）。

设 f ( i ) : f(i): f(i): 树大小为 i i i 的合法方案数。

树根肯定是定了的，然后从剩下的 i − 1 i-1 i−1 个数中选左子树大小个数，剩下自然都归为右子树。

f ( i ) = f ( s i z l s o n ) ∗ ( i − 1 s i z l s o n ) f(i)=f(siz_{lson})*binom{i-1}{siz_{lson}} f(i)=f(sizlson​)∗(sizlson​i−1​)。

组合数只是起分配编号的作用，分配后离散化成 1 , 2 , . . . , j 1,2,...,j 1,2,...,j。

比如：对于 f ( 5 ) f(5) f(5) 而言，根是 1 1 1， p ( 1 ) = 1 p(1)=1 p(1)=1 是固定的。

但是分给左子树的编号可能是 ( 2 , 3 , 4 ) , ( 2 , 3 , 5 ) , ( 2 , 4 , 5 ) , ( 3 , 4 , 5 ) (2,3,4),(2,3,5),(2,4,5),(3,4,5) (2,3,4),(2,3,5),(2,4,5),(3,4,5) 有四种情况。

但是离散化后都是 ( 1 , 2 , 3 ) (1,2,3) (1,2,3)。

而 f ( 3 ) f(3) f(3) 计算的就是当其被分配的编号为 ( 1 , 2 , 3 ) (1,2,3) (1,2,3) 的时候的方案数。

这里面是嵌套下去的递归过程，分配编号方案数，拿到离散化的编号，继续往字数分配编号…直到树大小为 1 / 2 / 3 1/2/3 1/2/3，再开始层层回溯计算总方案数。

整个问题编号为 1 ∼ n 1sim n 1∼n，离散化后也是 1 ∼ n 1sim n 1∼n，所以 f ( n ) f(n) f(n) 没有分配编号的多种方案数。

所以 f ( i ) f(i) f(i) 只是计算分配给其的离散化的连续编号然后是小根堆的答案。

这里的坑点是 n n n 可能 > m >m >m。所以预处理阶乘和逆元要注意上限的限制到底是多少。

#include 
using namespace std;
#define int long long
#define maxn 1000005
int n, p;
int fac[maxn], inv[maxn], siz[maxn], f[maxn], lg[maxn];

int qkpow( int x, int y ) {
    int ans = 1;
    while( y ) {
        if( y & 1 ) ans = ans * x % p;
        x = x * x % p;
        y >>= 1;
    }
    return ans;
}

int calc( int n, int m ) {
    if( n < m ) return 0;
    else return fac[n] * inv[m] % p * inv[n - m] % p;
}

int C( int n, int m ) {
    if( ! m ) return 1;
    return C( n / p, m / p ) * calc( n % p, m % p ) % p;
}

#define lson i << 1
#define rson i << 1 | 1

signed main() {
    scanf( "%lld %lld", &n, &p );
    fac[0] = inv[0] = 1, lg[0] = -1;
    for( int i = 1;i <= n;i ++ ) lg[i] = lg[i >> 1] + 1;
    int lim = min( n, p - 1 );
    for( int i = 1;i <= lim;i ++ ) fac[i] = fac[i - 1] * i % p;
    inv[lim] = qkpow( fac[lim], p - 2 );
    for( int i = lim - 1;i;i -- ) inv[i] = inv[i + 1] * ( i + 1 ) % p;
    f[1] = f[2] = 1, f[3] = 2;
    for( int i = 4, l = 1, r = 1;i <= n;i ++ ) {
        if( i - (1 << lg[i]) + 1 <= (1 << lg[i] - 1) ) l ++;
        else r ++;
        f[i] = C( i - 1, l ) * f[l] % p * f[r] % p;
    }
    printf( "%lldn", f[n] % p );
    return 0;
}