一、题意理解

我们要计算的是 烷基 (alkyl group) 的同分异构体数目。

化学背景：

• 烷基：烷烃分子去掉一个氢原子后剩下的部分，通式 $C_n H_{2n+1}$。
• 碳原子形成四价键，在烷基中，连接其它碳原子的键最多3个（因为有一个键连接母体烷烃）。
• 题目要求：$n$ 个碳原子的烷基同分异构体数目。

二、转化为图论问题

将碳原子看作节点，碳碳键看作边：

• 每个节点度数 ≤ 4（碳四价）
• 根节点度数 ≤ 3（因为一个键连接母体）
• 其它节点度数 ≤ 4
• 树结构（烷烃是无环的）

所以问题转化为： 求 $n$ 个节点的有根树数目，根度数 ≤ 3，其它节点度数 ≤ 4。

三、动态规划思路

设 $dp[n]$ 表示 $n$ 个节点的有根树数目（根度数 ≤ 3）。

考虑根的子树分配：

• 根可以有 0, 1, 2, 3 棵子树
• 每棵子树也是一个烷基（根度数 ≤ 3）
• 子树之间无序（因为化学上对称子树交换不产生新异构体）

1. 生成函数方法

设 $A(x) = \sum_{i=0}^\infty dp[i] x^i$，其中 $dp[0]=1$（空树）。

对于根：

• 0棵子树：1 种（只有根）
• 1棵子树：$A(x)$
• 2棵子树：$\frac{A(x)^2 + A(x^2)}{2}$（Burnside引理，考虑对称性）
• 3棵子树：$\frac{A(x)^3 + 3A(x)A(x^2) + 2A(x^3)}{6}$（Burnside引理）

所以： $ A(x) = 1 + x \left[ A(x) + \frac{A(x)^2 + A(x^2)}{2} + \frac{A(x)^3 + 3A(x)A(x^2) + 2A(x^3)}{6} \right] $ 这里乘以 $x$ 是因为根节点占用一个碳原子。

2. 递推计算

我们可以用 DP 直接计算 $dp[n]$：

设 $dp[i]$ 表示 $i$ 个碳的烷基数目。

枚举根的子树情况：

• 1棵子树：$dp[i-1]$（子树用掉 $i-1$ 个碳）
• 2棵子树：枚举第一棵子树大小 $a$，第二棵大小 $b$，$a+b = i-1$，且 $a \ge b$：
  • 如果 $a \neq b$：方案数 $dp[a] \cdot dp[b]$
  • 如果 $a = b$：方案数 $\binom{dp[a]+1}{2}$（可重复组合）
• 3棵子树：枚举三棵子树大小 $a,b,c$，$a+b+c = i-1$，且 $a \ge b \ge c$：
  • 三个不同：$dp[a] \cdot dp[b] \cdot dp[c]$
  • 两个相同：$dp[a] \cdot \binom{dp[b]+1}{2}$（$a > b = c$）
  • 三个相同：$\binom{dp[a]+2}{3}$（$a = b = c$）

最后对所有情况求和得到 $dp[i]$。

四、算法步骤

1. 初始化 $dp[0] = 1$（空树）
2. 对于 $i = 1$ 到 $n$：
   • 初始化 $dp[i] = 0$
   • 1棵子树：$dp[i] += dp[i-1]$
   • 2棵子树：
     • 枚举 $a = \lceil \frac{i-1}{2} \rceil$ 到 $i-1$，$b = i-1-a$，且 $a \ge b \ge 0$
       • 如果 $a > b$：$dp[i] += dp[a] \cdot dp[b]$
       • 如果 $a = b$：$dp[i] += C(dp[a] + 1, 2)$
   • 3棵子树：
     • 枚举 $a$ 从 $\lceil \frac{i-1}{3} \rceil$ 到 $i-1$
       • 枚举 $b$ 从 $\lceil \frac{i-1-a}{2} \rceil$ 到 $\min(a, i-1-a)$
         • $c = i-1-a-b$，且 $c \le b$
         • 如果 $a > b > c$：$dp[i] += dp[a] \cdot dp[b] \cdot dp[c]$
         • 如果 $a > b = c$：$dp[i] += dp[a] \cdot C(dp[b] + 1, 2)$
         • 如果 $a = b > c$：$dp[i] += C(dp[a] + 1, 2) \cdot dp[c]$
         • 如果 $a = b = c$：$dp[i] += C(dp[a] + 2, 3)$
3. 输出 $dp[n]$

其中 $C(n, k) = \binom{n}{k}$ 模 $10^9+7$。

五、代码实现（C++）

#include <bits/stdc++.h>
#define up(i,l,r) for(int i=(l);i<=(r);++i)
#define down(i,l,r) for(int i=(l);i>=(r);--i)
#define pi pair<int,int>
#define p1 first
#define p2 second
#define m_p make_pair
#define p_b push_back
#define ppc __builtin_popcount
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double db;
const db eps = 1e-5;
const int maxn = 1e6 + 10, mod = 1e9 + 7, iv6 = 166666668, iv2 = 5e8 + 4;
inline ll read() {
    ll x = 0;
    short t = 1;
    char ch = getchar();

    while (ch < '0' || ch > '9') {
        if (ch == '-')
            t = -1;

        ch = getchar();
    }

    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();

    return x * t;
}
int n, f[maxn];
void slv() {
    n = read();
    f[0] = 1;
    up(i, 1, n) {
        up(a, 0, i - 1)
        up(b, a, i - 1 - a) {
            int c = i - 1 - a - b;

            if (b > c)
                continue;

            if (a == b && b == c)
                f[i] = (f[i] + f[a] * 1llu * (f[a] + 1) % mod * 1llu * (f[a] + 2) % mod * 1llu * iv6) % mod;
            else if (a == b)
                f[i] = (f[i] + f[a] * 1llu * (f[a] + 1) % mod * 1llu * f[c] % mod * 1llu * iv2) % mod;
            else if (b == c)
                f[i] = (f[i] + f[a] * 1llu * f[b] % mod * 1llu * (f[b] + 1) % mod * 1llu * iv2) % mod;
            else
                f[i] = (f[i] + f[a] * 1llu * f[b] % mod * 1llu * f[c]) % mod;
        }
    }
    cout << f[n];
}
int main() {
    // freopen("1.in","r",stdin),freopen("1.out","w",stdout);
    // int t=read();while(t--)slv();
    slv();
    cerr << clock() * 1.0 / CLOCKS_PER_SEC << "s\n";
    return 0;
}

六、样例验证

输入 $n=6$，输出 $17$，与题目表格一致。

七、总结

本题的关键在于：

1. 将化学问题转化为有根树计数问题。
2. 根据碳原子价键限制确定节点度数约束。
3. 使用动态规划枚举根的子树分配情况。
4. 利用组合数学处理对称子树的情况（Burnside引理）。