51nod1805 小树 prufer序列 + 容斥原理

首先考虑$prufer$序列，那么问题转化为求

一个长为$n - 2$的序列，总共有$n$个元素，恰有$m$个元素不出现在序列中的方案数

考虑容斥，答案即为至少$m$个元素不出现 - 至少$m + 1$个不出现 + 至少$m + 2$个不出现......

至少$m$个元素不出现的方案数为$C(n, m) * (n - i)^{n - 2}$

接着考虑容斥系数，通过数学归纳法，我们发现是$C(i, m)$

然后就没了，复杂度$O(n \log n)$

注：$n = 1$或者$n = 2$时，树没有$prufer$序列，记得特判

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

#define ri register int

#define sid 1005000

#define mod 1000000007

int n, m, ans;

int inv[sid], fac[sid];

void Init_C() {

    fac[] = inv[] = fac[] = inv[] = ;

    for(ri i = ; i <= n; i ++) {

        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;

        fac[i] = 1ll * fac[i - ] * i % mod;

    }

    for(ri i = ; i <= n; i ++)

    inv[i] = 1ll * inv[i] * inv[i - ] % mod;

}

int C(int n, int m) {

    if(n < m) return ;

    return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;

}

int fp(int a, int k) {

    int ret = ;

    for( ; k; k >>= , a = 1ll * a * a % mod)

    if(k & ) ret = 1ll * ret * a % mod;

    return ret;

}

int main() {

    cin >> n >> m;

    if(n ==  || n == )

    { printf("1\n"); return ; }

    Init_C();

    for(ri i = m, j = ; i <= n; i ++, j *= -) {

        ans += (1ll * j * C(i, m) * C(n, i) % mod * fp(n - i, n - ) % mod);

        if(ans < ) ans += mod; if(ans >= mod) ans -= mod;

    }

    printf("%d\n", ans);

    return ;

}

巴特西

51nod1805 小树 prufer序列 + 容斥原理

最新文章

热门文章