一个化学题(or 数数题?)

回复帖子

@StudyingFather 2019-05-14 22:18 回复

刚刚在群里讨论一道化学题:满足同一分子式的烃的同分异构体究竟有多少种?

更一般地,如果把烃换成卤代烃的话,有没有比较高效的方法算出卤代烃的数量?

欢迎各位神仙一块讨论一下QAQ

@MC_OMG 2019-05-14 22:22 回复

初一没咋学化学の蒟蒻路过

@LinkedIn 2019-05-14 22:25 回复

这东西还有公式?

先碳链异构再官能团异构...

@Conical 2019-05-14 22:33 回复

不考虑特殊情况,本质是上一类树计数,暴力 dp 是 $n^2$ 的,利用生成函数 + 分治 FFT 可以做到 $n\log^n$,牛顿迭代法就是一个 $\log$ 了。可以参见 loj6538.