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;
}