[ABC276G] Count Sequences 题解

考虑差分，设 \(d_i=a_i-a_{i-1}\)，特别的，\(d_1=a_1\)，那么约束就变成了

1. \(\displaystyle\sum d_i\le m\)。
2. 对所有 \(i>1\) 有 \(d_i\not\equiv 0\pmod 3\)。

发现 \(d_1\) 非常特殊，于是可以单独考虑 \(d_1\equiv 0\pmod 3\)。以下设 \(d_1\not\equiv 0\pmod 3\)，\(d_1\equiv 0\pmod 3\) 同理。

那么 \(d_i\) 只能是 \(3k+1\) 或 \(3k+2\) 的形式。考虑枚举形如 \(3k+2\) 的 \(d_i\) 的数量，设其为 \(c\)，那么 \(3k+1\) 形式的数的数量即为 \(n-c\)，方案数为 \(\displaystyle{n\choose c}\)。于是剩下的步骤相当于将不超过 \(\lfloor\dfrac{m-2c-(n-c)}{3}\rfloor\) 组物品放置在 \(n\) 个箱子内，这玩意可以插板+前缀和预处理。