题解：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. 只有一个二类
  2. 先有一个二类，后有一个三类
  3. 先有一个三类，后有一个二类
  4. 按照三-二-三方法放了三块板

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

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