LOJ6269 烷基计数加强版题解

题意：众所周知，大连 24 中是一所神奇的学校，在那里，化竞的同学很多都擅长写代码。

有一天，化学不及格的胡小兔向化竞巨佬晴岚请教化学题：

“$n$ 个碳原子的烷基共有多少种同分异构体？”

刚刚得了化竞全市第一的晴岚听了，认为这道题十分简单，建议胡小兔写个程序解决这个问题。但胡小兔弱得连什么是同分异构体都不知道，于是晴岚给胡小兔画了个图——例如 $n=4$ 时 (即丁基)，有 $4$ 种同分异构体：

同理，其他常见烷基同分异构体数目如下表：

n 1 2 3 4 5 6

同分异构体数目 1 1 2 4 8 17

现在已知碳原子个数 $n$，求对应的烷基有多少种同分异构体。

答案对 $10^9 + 7$ 取模。

数据范围： $n \le 5\times 10^3$

注意：这里的烷基计数不用考虑空间异构，能否稳定存在等各种特殊情况。也就是说，你要求的是 $n$ 个点的每个点度数不超过 $4$ 且根的度数不超过 $3$ 的有根树的数目。

n	1	2	3	4	5	6
同分异构体数目	1	1	2	4	8	17

据说这种叫：无标号树计数题

最优的解法是 $O(n \log^2 n)$ 的，涉及Pólya原理和生成函数，这里暂且不提。

首先考虑弱化版 #6185. 烷基计数的dp （ $n \le 400$ ）

设 $f_i$ 表示 $i$ -烷基的个数，然后枚举三个子树的大小，乘个组合数就好了

实际上因为 $s_1+s_2+s_3=i-1$ ，因此只用枚举两个子树的大小

时间复杂度 $O(n^3)$ ，可以过弱化版。

考虑这道题怎么做

刚刚的dp瓶颈在于枚举了所有的子树大小

还记得树上背包吗？我们也有很多子树，但是我们是一个个子树添加的，而不是枚举每个子树的大小。

因此可以尝试像树上背包一样，一个个子树的添加

可是这道题的子结点没有区别，因此我们按子树大小顺序一一添加

枚举一个 $\mathtt{sz}$ （从 $1$ 到 $n$ ），然后去对所有的dp值产生贡献

或者等价地，在dp中加上一维 $s$ 表示当前允许的子树大小

同时我们还要记录当前根节点的度数

设 $f_{s,i,j}$ 表示 $i$ -烷基，根节点度数为 $j$ ，所有子树的大小不超过 $s$ 的方案数

考虑转移。首先，如果所有子树的大小都小于 $s$ ，则答案为 $f_{s-1,i,j}$

否则设存在 $k$ 个子树的大小为 $s$ ，显然 $1\le k \le \min\left\{j,\left\lfloor{\frac{i-1}{s}}\right\rfloor\right\}$ ，

把这些子树去掉以后，剩下 $i-sk$ 个点，根节点的度数为 $j-k$ ，且剩余子树大小均不超过 $s-1$

对应到状态就是 $f_{s-1,i-sk,j-k}$

然后就是考虑这 $k$ 个子树的分布，或者说把这 $k$ 个子树插进去

设大小为 $s$ 的子树有 $c(c=\sum f_{s-1,s,j})$ 个（显然这 $c$ 个本质不同）

那么这就是一个可重组合，方案数为 $\dbinom{c+k-1}{k}$ （ $c$ 个选 $k$ 个，可重复）

则完整转移方程为

$f_{s,i,j} = \sum_{0 \le k \le j \land sk < i} f_{s-1,i-sk,j-k} \times\dbinom{c+k-1}{k}$

时间复杂度 $O(n^2m \log m)$ ，其中 $m$ 为度数的限制，即 $4$ 。

然后这个第一维显然可以滚动数组。故空间复杂度为 $O(nm)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(5e3+15))
#define M 4

const int mod=1e9+7,inv6=(mod+1)/6;
int n,f[N][M];
void add(int &x,int y){ (x+=y) >= mod? x-=mod : 0;}
int C(int n,int m)
{
    switch(m)
    {
        case 0: return 1;
        case 1: return n % mod;
        case 2: return n*(n-1)/2 % mod;
        default: return n*(n-1) % mod * (n-2) % mod * inv6 % mod;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    f[1][0]=1;
    for(int sz=1,cur; sz<n; ++sz)
    {
        cur = 0; for(int i=0; i<M; i++) add(cur,f[sz][i]);
        for(int i=n; i>=1; i--)
            for(int j=1; j<M; j++)
                for(int k=1; k<=j && sz*k<i; k++)
                    add(f[i][j],f[i-sz*k][j-k]*C(cur+k-1,k)%mod);
    }
    int res=0; for(int i=0; i<M; i++) add(res,f[n][i]);
    cout << res << '\n';
    return 0;
}