Description
众所周知，大连 24 中是一所神奇的学校，在那里，化竞的同学很多都擅长写代码。
有一天，化学不及格的胡小兔向化竞巨佬晴岚请教化学题：
“n 个碳原子的烷基共有多少种同分异构体？”
刚刚得了化竞全市第一的晴岚听了，认为这道题十分简单，建议胡小兔写个程序解决这个问题。但胡小兔弱得连什么是同分异构体都不知道，于是晴岚给胡小兔画了个图——例如 n=4 时（即丁基），有 4 种同分异构体：
同理，其他常见烷基同分异构体数目如下表：
| n | 1 | 2 | 3 | 4 | 5 | 6 |
| 同分异构体数目 | 1 | 1 | 2 | 4 | 8 | 17 |
现在已知碳原子个数 n，求对应的烷基有多少种同分异构体。
P.S. 2017.11.30更新：化竞巨佬晴岚高二进国集保送北大了……
Input
输入一行，一个整数 n，表示烷基中碳原子的数目。
Output
输出该烷基同分异构体的数目，对 10^9+7 取模。
Sample Input
6
Sample Output
17
Hint
1≤n≤400
注意：这里的烷基计数不用考虑空间异构，能否稳定存在等各种特殊情况。也就是说，你要求的是 n 个点的每个点度数不超过 4 且根的度数不超过 3 的有根树的数目。
题解
按照“二叉树个数”的思路，我们可以枚举每个节点儿子子树的大小来做。
值得注意的是，这棵树的儿子是无序的所以不能简单用乘法原理相乘。记 $f_k$ 为子树大小为 $k$ 的生成树的个数。记其三个儿子大小为 $i,j,p$ 显然 $i+j+p = k-1$ 。不妨设 $i <= j <= p$。
满足：
$$f_k =
\begin{cases}
C_{f_i+3-1}^3& \text{i = p}\\
C_{f_i+2-1}^2*f_p& \text{i = j}\\
C_{f_j+2-1}^2*f_i& \text{j = p}\\
f_i*f_j*f_p& \text{otherwise}
\end{cases}$$
其中形同 $C_{n+m-1}^m$ 是可重复的组合数。
//It is made by Awson on 2018.1.2
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
const int N = ;
const int MOD = 1e9+; int n;
int f[N+]; int quick_pow(int x, int y) {
int ans = ;
while (y) {
if (y&) ans = (LL)ans*x%MOD;
x = (LL)x*x%MOD, y >>= ;
}
return ans;
}
void work() {
scanf("%d", &n);
f[] = ;
for (int k = ; k <= n; k++)
for (int i = ; i <= k; i++)
for (int j = i; j <= k; j++) {
int p = k--i-j; if (p < j) break;
if (i == p) (f[k] += (LL)f[i]*(f[i]+)%MOD*(f[i]+)%MOD*quick_pow(, MOD-)%MOD) %= MOD;
else if (i == j) (f[k] += (LL)f[i]*(f[i]+)%MOD*quick_pow(, MOD-)%MOD*f[p]%MOD) %= MOD;
else if (j == p) (f[k] += (LL)f[p]*(f[p]+)%MOD*quick_pow(, MOD-)%MOD*f[i]%MOD) %= MOD;
else (f[k] += (LL)f[i]*f[j]%MOD*f[p]%MOD) %= MOD;
}
printf("%d\n", f[n]);
}
int main() {
work();
return ;
}