luoguP4492 [HAOI2018]苹果树组合计数 + dp

首先，每个二叉树对应着唯一的中序遍历，并且每个二叉树的概率是相同的

这十分的有用

考虑\(dp\)求解

令\(f_i\)表示\(i\)个节点的子树，根的深度为\(1\)时，所有点的期望深度之和（乘\(i!\)）的值

令\(g_i\)表示\(i\)个节点的子树，期望两两路径之和（乘\(i!\)）的值

那么\(f_i = i * i! + \sum \limits_{L = 0}^{i - 1} \binom{i - 1}{L} (f_L * R! + f_R * L!)\)，\(L, R\)分别表示左右子树的值

\(g_i = \sum \limits_{L = 0}^{i - 1} \binom{i - 1}{L} (g_L * R! + g_R * L! + f_L * R! * (R + 1) + f_R * L! * (L + 1))\)

复杂度\(O(n^2)\)

由于没有逆元，因此组合数要预处理

好像可以用多项式优化到\(O(n \log^2 n)\)QAQ

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define ri register int

#define rep(io, st, ed) for(ri io = st; io <= ed; io ++)

#define drep(io, ed, st) for(ri io = ed; io >= st; io --)

const int sid = 2e3 + 5;

int n, mod;

int C[sid][sid], fac[sid], f[sid], g[sid];

inline void inc(int &a, int b) { a += b; if(a >= mod) a -= mod; }

inline void dec(int &a, int b) { a -= b; if(a < 0) a += mod; }

inline int Inc(int a, int b) { return (a + b >= mod) ? a + b - mod : a + b; }

inline int Dec(int a, int b) { return (a - b < 0) ? a - b + mod : a - b; }

inline int mul(int a, int b) { return 1ll * a * b % mod; }

inline void init() {

    fac[0] = C[0][0] = 1;

    rep(i, 1, n) {

        C[i][0] = C[i][i] = 1;

		fac[i] = mul(fac[i - 1], i);

        rep(j, 1, i - 1) C[i][j] = Inc(C[i - 1][j], C[i - 1][j - 1]);

    }

}

inline void dp() {

    f[1] = 1;

    rep(i, 2, n) {

        rep(L, 0, i - 1) {

            int R = i - 1 - L, F = 0, G = 0;

			F = (1ll * f[L] * fac[R] + 1ll * f[R] * fac[L]) % mod;

            G = (1ll * f[L] * fac[R] % mod * (R + 1) % mod);

			inc(G, 1ll * f[R] * fac[L] % mod * (L + 1) % mod);

			inc(G, 1ll * g[L] * fac[R] % mod);

			inc(G, 1ll * g[R] * fac[L] % mod);

            inc(f[i], mul(F, C[i - 1][L])); inc(g[i], mul(G, C[i - 1][L]));

        }

		inc(f[i], 1ll * i * fac[i] % mod);

    }

    printf("%d\n", g[n]);

}

int main() {

    cin >> n >> mod;

    init(); dp();

    return 0;

}

巴特西

luoguP4492 [HAOI2018]苹果树组合计数 + dp

最新文章

热门文章

巴特西

luoguP4492 [HAOI2018]苹果树 组合计数 + dp

最新文章

热门文章

luoguP4492 [HAOI2018]苹果树组合计数 + dp