P2606 [ZJOI2010]排列计数

因为每个结点至多有一个前驱，所以我们可以发现这是一个二叉树。现在我们要求的就是以1为根的二叉树中，有多少种情况，满足小根堆的性质。

设\(f(i)\)表示以\(i\)为根的子树中满足小根堆性质的情况，那么就有：\(f(i)=f(ls)*f(rs)*C_{sum(i)-1}^{sum(ls)}\)。表示选出\(sum(ls)\)个结点来作为左儿子中的结点，并且左右儿子都满足小根堆的性质。这里左右儿子这两个问题都是独立的，所以可以直接运用乘法原理。

这里求组合数可以直接用Lucas定理来求，Lucas定理为：若p是一个质数，那么\(C_n^m=C_{\frac{n}{p}}^{\frac{m}{p}}*C_{n\mod p}^{m\mod p}\mod p\)。

代码如下:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll ;

const int N = 2e6 + 5;

ll n, p;

ll inv[N], fac[N], s[N], f[N];

ll C(ll a, ll b) {

    if(a < b) return 0;

    if(a == b || b == 0) return 1;

    if(a < p && b < p) return inv[b] * inv[a - b] % p * fac[a] % p;

    return C(a % p, b % p) * C(a / p, b / p) % p;

}

ll qp(ll a, ll b) {

    ll ans = 1;

    while(b) {

        if(b & 1) ans = ans * a % p;

        a = a * a % p;

        b >>= 1;

    }

    return ans ;

}

int main() {

    cin >> n >> p;

    fac[0] = 1;

    for(int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % p;

    for(int i = 1; i <= n; i++) inv[i] = qp(fac[i], p - 2) ;

    for(int i = 1; i <= n; i++) s[i] = 1;

    for(int i = n; i >= 2; i--) s[i >> 1] += s[i] ;

    for(int i = n; i >= 1; i--) {

        int ls = i << 1, rs = i << 1 | 1;

        if(f[ls] && f[rs]) f[i] = f[ls] * f[rs] % p * C(s[i] - 1, s[ls]) % p;

        else if(f[ls]) f[i] = f[ls] ;

        else f[i] = 1;

    }

    cout << f[1] ;

    return 0;

}

巴特西

P2606 [ZJOI2010]排列计数

P2606 [ZJOI2010]排列计数

最新文章

热门文章