Skip to main content

__debug's Home Keep it simple, stupid

计算烷烃的同分异构体个数 (结构异构)

本质上就是一个无标号无根树带度数限制的计数问题.

将问题一般化:

求 \(n\) 个点的无标号无根树的个数, 且每个点的度数不超过 \(m\).


烷基 (有根树)

首先考虑计算烷基的个数 (即有根树).

考虑暴力 DP. 设状态为 \(f(i, j, k)\), 表示当前共有 \(i\) 个点, 最大的子树大小为 \(j\), 且根的度数为 \(k\). 对于状态 \(f(i, j, k)\), 通过枚举最大子树的个数 \(l\) 和次大子树的大小 \(size\), 有 $$f(i, j, k) = \sum_{l} \sum_{s} + f(i - j l, size, k - l) \binom{s + l - 1}{l}$$ 其中 \(s = \sum_{a = 1}^{j} \sum_{b = 0}^{m - 1} f(j, a, b)\), 组合数是用来可重集计数的.

这是 \(O(n^3 m^2)\) 的. 显然可以前缀和优化, 但是空间撑不住. 还可以做得更好.

考虑如何省掉 \(j\) 这一维状态. 即设状态为 \(f(i, j)\), 表示当前共有 \(i\) 个点, 根的度数为 \(k\).

考虑 DP 的一个技巧: 强行规定转移顺序. 即, 先 \(1 ... n\) 枚举 \(size\), 表示强制用最大子树大小为 \(size\) 的情形来转移. 不妨设 \(s = \sum_{k = 0}^{m - 1} f(size, k)\), 那么对于一个 \(f(i, j)\), 再枚举一个最大子树 (即子树大小为 \(size\) 的子树) 的个数 \(k\), 我们便有转移 $$f(i, j) \leftarrow f(i, j) + f(i - size \times k, j - k) \binom{s + k - 1}{k}$$ 这是 \(O(n^2m^2)\) 的. 如果是算烷基的话, 便是 \(O(n^2)\) 的.

烷烃 (无根树)

本来我想枚举主链长度来做的, 后来发现直接利用树的重心来做非常方便.

首先只要某个点 \(u\) 满足其子树大小都 \(\leq \frac{n}{2}\), 那么这个点是这颗树的重心. 比较显然的是, 重心最多只会有两个, 并且有两个重心的情形, 两个重心一定相邻, 并且另一个重心做根的时候, 这个重心的子树大小为 \(\frac{n}{2}\). (当然 \(n\) 必须要是偶数)

然后很多无根树同构的问题就可以通过重心转化为有根树同构. 烷烃就可以这么计数. 因为我们可以在 DP 烷基的时候, 强制 \(size < \frac{n}{2}\) (注意是小于), 这样求出的 \(f(i, j)\) 就是点数为 \(i\) 且重心度数为 \(j\) 的无根树个数. 那么答案为 $$\sum_{k = 0}^{m} f(n, k) + [n \bmod 2 = 0] \binom{\sum_{k = 0}^{m - 1} f(\frac{n}{2}, k) + 1}{2}$$

前一项为一个重心的情形, 后一项为两个重心的情形.

附上代码:

def C(n, k):
    ret = 1
    for i in range(k):
	ret *= n - i
    for i in range(1, k + 1):
	ret //= i
    return ret

def calc(n, m):
    dp = [[0 for i in range(m + 1)] for i in range(n + 1)]
    dp[1][0] = 1
    for size in range(1, (n - 1) // 2 + 1):
	s = sum(dp[size][:-1])
	for i in range(n, size, -1):
	    for j in range(1, m + 1):
		for k in range(1, j + 1):
		    if size * k < i:
			dp[i][j] += dp[i - size * k][j - k] * C(s + k - 1, k)
    ret = sum(dp[n])
    if n % 2 == 0:
	ret += C(sum(dp[n // 2][:-1]) + 1, 2)
    return ret

n = int(input())
print(calc(n, 4))

后记

2333 烷的同分异构体数目:

157038601417900383491507313007126476929901128584980929040328564849673887301892838
989186719155295065780648805033323799081644261605416814576472429379570446105754153
032938434875321267357805326803968637014261072831833140303053886507281208719159470
584667239945272086443538093325305572999484709867460292139543868125116933739415887
693141588951357813605287018512073931967035540527385446280753281514034950843167833
579841829019200324486114406621480237026159133298456345071826780785060954897227558
066297981150127327947643903659044344306347335991363027674523894081368188448651669
748389175422401130181866583892517974531049838294909782753346041553257628575183443
460842226438839583913777751344365602933263903955025671242419474649565802976699868
209024028058760342653477214185651508671271885274691507489975757967768599554387712
148041382611707905442120123456078525116265346902467636213905912118143991150845447
663354069338813286629769072909661698283035418492319137445705757455928938075805963
762085594694393096226567509132572289534634464264144718230717818448681

这个问题还有生成函数的解法, 留坑待填.

顺便丢几个有用的链接

Comments

Comments powered by Disqus