olefin

给定一个长度为 \(n\) 的01字符串

烯烃不存在连续两个碳碳双键出现的情况，因此可以把原来的序列分成若干个01交替序列，相邻之间用多个0隔开，这些序列之间不会干扰

一个包含 \(n\) 个碳碳双键的交替序列加成 \(k\) 次的方案数为 \(\displaystyle \binom{n+k}{n-k}\prod_{i=1}^{k} (2i-1)\)

证明思路：

一共有 \(\displaystyle \binom{n+k}{n-k}\) 种可能的结束状态

且任何一个合法状态均有 \(\prod_{i=1}^m (2i-1)\) 种可能的构造方法

可以从0次操作开始向上归纳，对于一个 \(k\) 次操作的状态，合法的逆操作一定是一段 两端是0的极长的 交替序列，容易通过次数分析发现此时合法的极长交替序列就只有 \(2k-1\) 个，即完成从上层的归纳

按照这个式子，分治 \(\text{NTT}\) 即可