题解：AT_arc124_e [ARC124E] Pass to Next

题意简述：对于一个序列 $\{a_n\}$，计算满足以下条件的 $\{b_n\}$ 的 $\prod b_i$ 之和：存在一个序列 $\{d_n\}$，使得这三个序列满足以下性质：

特别地，定义 $d_0=d_n$。

考虑这样一个形式化的题意可以如何表示。

下文设 $\sum a_i$ 为 $m$。对于一个不可旋转的圆环，我们可以将所有的序列 $\{a_n\}$ 映射为一个圆上有 $m+n$ 个点的 $n-$ 切分。$n-$ 切分在此处的定义是：在环上选择 $n$ 个不同的间隔插入一类板，使得环按顺序断为 $n$ 段。

于是我们可以将 $d_i$ 映射为在第 $i-1$ 个一类板与第 $i$ 个一类板之间（包括第 $i-1$ 个一类板的位置，但不包括第 $i$ 个），选择一个位置插入二类板，板的位置距离第 $i$ 个一类间隔板为 $d_i+1$。

而套路地，此时 $\prod b_i$ 也就可以表示为在相邻两个二类板之间（两侧均不包含）插入一个三类板的方案数。

转化成经典插板模型，这就变成了一个好做的问题。题目相当于已经钦定了第一类板的位置，于是我们对第 $i$ 个第一类板所在位置（含）到第 $i+1$ 个第一类板位置（不含）所对区间的二、三类板放置情况分类。显然它只有以下 $4$ 种情况：

这些情况之间的贡献关系是明确的，因为二类板和三类板必然交替放置。而每种情况内部的系数可以通过组合数容易地计算。因此从第 $1$ 个区间开始线性 dp ，最后对于第 $n$ 个区间和第 $1$ 个区间的贡献直接合并即可，复杂度 $O(n)$。

*关于组合数计算：对于你要计算的 $C_n^m$，虽然 $n$ 很大，但是 $m\le 3$，因此直接算就可以了。