「Loj 6185」烷基计数 (计数DP，无标号有根树统计)

Loj 6185
题意：求$n$个点的每个点度数不超过$4$且根的度数不超过$3$的有根树的数目。

显然有一个暴力DP方法，复杂度取决于根度数

考虑$dp$一颗一颗子树加进去方案，从小到大加可以不重不漏。
这里我们设$dp(s,i,j)$为当前添加的子树大小不超过$s$，有$i$个节点，根节点$j$度的方案数。

考虑枚举添加的子树个数$k$，那么这$k$个$s$大小的子树占用了$ks$个节点和$k$度，那么可以从$dp(s-1,i-ks,j-k)$转移过来。然后考虑将$k$棵子树乘上他们的方案。

设$a_i=\sum\limits_{g=0}^{m-1} dp(s-1, i, g)$，那么$a_s$就是$s$大小子树的方案‘
考虑将$k$棵子树分成$a_s$份(可以留空)，方案数为$C^{a_s-1}_{a_s+k-1}$

那么得到转移方程
$$
dp(s,i,j)=\sum_{k=0}^{k \leq j, ks - 1 \leq i} dp(s-1,i-ks,j-k) \cdot C^{k}_{a_s+k-1}
$$

由于$a_s-1$较大，而$k \leq m=3$, 则转化一下方便求组合数。
注意到第一维可以不需要存储，类似背包滚动数组的方法，所以$i$要倒序

时间复杂度$O \left( n^2 m \log m \right)$。

知识点：
1、计数DP要按顺序加才能不重不漏
2、有根树统计可以用加子树的顺序

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MAXN = 405, MO = 1e9 + 7;

    LL n, m = 4, dp[MAXN][7], inv2 = 500000004, inv6 = 166666668;

    LL C(LL n, LL m) {

        if (m > n) return 0;

        if (m == 0) return 1;
        if (m == 1) return n;
        if (m == 2) return n * (n - 1ll) % MO * inv2 % MO;
        if (m == 3) return n * (n - 1ll) % MO * (n - 2ll) % MO * inv6 % MO;

        return 0;
    }

    void clean() {
    }
    int solve() {

        clean();
        cin >> n;
        dp[1][0] = 1;
        for (int s = 1; s < n; ++s) {

            LL a = 0;
            for (int g = 0; g < m; ++g) a = (a + dp[s][g]) % MO;

            for (int i = n; i ; --i) {
                for (int j = 1; j < m; ++j) {
                    for (int k = 1; k <= j && k * s < i; ++k) {
                        dp[i][j] = (dp[i][j] + dp[i - k * s][j - k] * C(a + k - 1, k) % MO) % MO;
                    }
                }
            }
        }

        LL ans = 0;
        for (LL i = 0; i <= m; ++i) ans = (ans + dp[n][i]) % MO;

        cout << ans;

        return 0;
    } 
}
int main() {
    flyinthesky::solve();
    return 0;
}