P7275

最终方案肯定是将 $[1,n]$ 划分为若干个长度 $\ge 2$ 的区间 $[l_i,r_i]$ 满足 $l_i\sim r_i$ 按照 $l_i\to l_i+1\to l_i+2\to\cdots\to r_i$ 的方案连成一条链，剩余点之间连边满足不存在其他边两端点差为 $1$。 考虑对后面 ......

快进完生成函数，现在我们知道如果令一个长度为 $i$ 的连续段权值为 $in[z^i]\frac{z^2}{1-z+z^2}$，一个连续段权值的 ogf 是 $F$，那么答案的 ogf 就是 $\frac{1}{1-F}$． 先看看 $\frac{z^2}{1-z+z^2}$ 展开，发现形式很好看， ......