一句话题意
求 \(n\) 个点的每个点度数不超过 \(4\) 且根的度数不超过 \(3\) 的有根树的数目。
题解
定义 \(F_{n,i}\) 为节点数为 \(n\)，根节点度数为 \(i\) 的个数。\(A_n\) 为节点数为 \(n\)个数，\(\displaystyle A_n = \sum_{i = 0}^3 F_{n,i}\)。
在转移的时候去考虑三棵子树的最大大小 \(k\)，从 \(k = 1\) 的情况开始讨论，每次转移相当于加上若干棵大小为 \(k\) 的子树。
但是并不能直接转移，假设大小为 \(k\) 的树共有 \(m\) 种，需要选取 \(3\) 棵。设 \(m = 3\)，将这三种情况分别标号为 \(1, 2, 3\),那么合法的情况为下表：
| 选择方案 |
|---|
| \(1, 1, 1\) |
| \(1, 1, 2\) |
| \(1, 1, 3\) |
| \(1, 2, 2\) |
| \(1, 2, 3\) |
| \(1, 3, 3\) |
| \(2, 2, 2\) |
| \(2, 2, 3\) |
| \(3, 3, 3\) |
之所以不是 \(3^3\) 种转移是因为子树的无序性，即 \(1, 1, 2\) 和 \(1, 2, 1\) 这两种方案是等价的。
可以发现一种枚举所有状态的可行办法是对方案进行标号，然后使选出的状态递增，那么我们可以先从选择 \(2\) 棵子树下手，去找寻一些规律。
| 选择方案 |
|---|
| \(1, 1\) |
| \(1, 2\) |
| \(1, 3\) |
| \(2, 2\) |
| \(2, 3\) |
| \(3, 3\) |
我们去枚举第一位的值，可以发现，如果第一位选择 \(1\)，那么有 \(3\) 个可能的第二位，如果第一位选择 \(2\)，那么有 \(2\) 个可能的第二位，如果第一位选择 \(3\)，那么有 \(1\) 种可能的第二位。
所以我们可以列出选择两棵子树时的通项公式：
\[\begin{aligned}G(x) & = \sum_{i=1}^{n}i \\ & = \frac{n \times (n + 1)}{2}\end{aligned} \]继续考虑选择 \(3\) 棵子树时的情况：
| 选择方案 |
|---|
| \(1, 1, 1\) |
| \(1, 1, 2\) |
| \(1, 1, 3\) |
| \(1, 2, 2\) |
| \(1, 2, 3\) |
| \(1, 3, 3\) |
| \(2, 2, 2\) |
| \(2, 2, 3\) |
| \(3, 3, 3\) |
我们可以枚举选择的第二位，可以发现，如果第二位选择 \(i\)，那么第一位有从 \(1\) 到 \(i\) 共 \(i\) 种情况，第 \(3\) 位则有从 \(i\) 到 \(m\) 共 \(m - i + 1\) 种情况，由此我们可以得到通项公式：
\[T(n) = \sum_{i = 1}^{n}i \times (n - i + 1) \]下面对该式进行化简：
\[\begin{aligned}T(n) & = \sum_{i = 1}^{n}i \times (n - i + 1) \\ & = n \sum_{i = 1}^{n}{1} - \sum_{i = 2}^{n} {i \times(i - 1)}\\ & = \frac{n^2 \times (n + 1)}{2} - \sum_{i = 1}^{n - 1}{i \times (i + 1)}\\ & = \frac{n^2 \times (n + 1)}{2} - \frac{n \times (n + 1)}{2} - \sum_{i = 1}^{n - 1}{i^2}\end{aligned}\]下面考虑如何化简 \(\sum_{i = 1}^{n - 1}{i^2}\)，我们可以看到
\[(a+1)^3-a^3=3a^3+3a+1 \]将 \(a\) 从 \(1\) 取到 \(n - 1\)，可以得到：
\[\begin{aligned} n^3-1^3 & =3\sum_{i = 1}^{n - 1}{i^2}+3\sum_{i = 1}^{n - 1}{i}+ n - 1\\ 3\sum_{i = 1}^{n - 1}{i^2}& = n^3-1 - 3\times\frac{n \times (n - 1)}{2}-n + 1\\ 6\sum_{i = 1}^{n - 1}{i^2}& = 2n^3 - 3\times{n \times (n - 1)}-2n\\ & = n\left[ 2n²-3(n - 1)-2 \right]\\ & = n(2n - 1)(n - 1)\\ \end{aligned}\]所以可以得到
\[\sum_{i = 1}^{n - 1}{i^2} = \frac{n(2n - 1)(n - 1)}{6} \]所以
\[\begin{aligned}T(n) & = \frac{n^2 \times (n + 1)}{2} - \frac{n \times (n + 1)}{2} - \frac{n(2n - 1)\times(n - 1)}{6}\\ & = \frac{3n^2 \times (n + 1)}{6} - \frac{3n \times (n + 1)}{6} - \frac{n(2n - 1)\times(n - 1)}{6}\\ & =\frac{3n^2 \times (n + 1)}{6} - \frac{2n \times (n - 1)\times(n + 1)}{6}\\ & = \frac{(3n - 2n + 2) \times n\times(n + 1)}{6}\\ & = \frac{(n + 2)\times(n + 1)\times n}{3\times 2}\\ & = \dbinom{n + 2}{3} \end{aligned}\]所以我们要干什么来着？哦对，转移DP，回顾一下：
定义 \(F_{n,i}\) 为节点数为 \(n\)，根节点度数为 \(i\) 的个数。\(A_n\) 为节点数为 \(n\)个数，\(\displaystyle A_n = \sum_{i = 0}^3 F_{n,i}\)。
我们卡一个当前所有树的最大的子树，每次转移的时候把相应大小的子树贡献塞到当前的DP计数数组中。
Code
#include<bits/stdc++.h>
typedef long long valueType;
constexpr int maxN = 5005;
constexpr valueType MIN = INT_MIN;
valueType MOD_;
valueType const &MOD = MOD_;
valueType Inv2_, Inv6_;
valueType const &Inv2 = Inv2_, &Inv6 = Inv6_;
std::array<std::array<valueType, maxN>, 4> dp;
valueType F(int x) {
return (dp[0][x] + dp[1][x] + dp[2][x] + dp[3][x]) % MOD;
}
valueType Pow(valueType base, valueType b) {
long long ans = 1;
while(b > 0){
if (b & 1)
ans = ans * base % MOD;
base = base * base % MOD;
b = b >> 1;
}
return ans;
}
valueType calc(valueType value, int x) {
if(x == 1)
return value;
if(x == 2)
return (value + 1) * value % MOD * Inv2 % MOD;
if(x == 3)
return (__int128) (value + 2) * (value + 1) * value * Inv6 % MOD;
}
int main() {
int N;
std::cin >> N >> MOD_;
Inv2_ = Pow(2, MOD - 2);
Inv6_ = Pow(6, MOD - 2);
dp[0][1] = 1;
for(int i = 1; i < N; ++i)
for(int j = N; j > i; --j)
for(int k = 1; k <= 3; ++k)
for(int l = 1; l <= k && l * i + k - l < j; ++l)
dp[k][j] = (dp[k][j] + (__int128)calc(F(i), l) * dp[k - l][j - i * l]) % MOD;
std::cout << F(N) << std::flush;
return 0;
}