abc276G - 洛谷保存站

# $abc 276 G \space \space Count \space Sequences$

## 前言
比赛的时候想了个阴间的容斥，调了 $1h$ 。
## 题意
计算满足以下条件的序列 $a$ 的数量：

1. 长度为 $n$ 。

2. $0\leq a_1 \leq a_2 \leq \dots \leq a_n \leq m$

3. $a_i\neq a_{i+1}(mod\space 3)$

## 题解

由相邻元素模 $3 $ 不同余可以想到差分。

设 $b_i=a_{i+1}-a_i(1\leq i\leq n-1)$ 。则 $b_i$ 一定可以表示为 $3x_i+y_i$ 的形式，其中 $1\leq y_i \leq 2 $ ， $x_i\geq 0$ 。

考虑在原题的限制下，$x$ 与 $y$ 有什么性质。

可以发现，$\sum_{i=1}^{n-1} y_i\leq m,\sum_{i=1}^{n-1} x_i\leq \lfloor \frac{m-\sum_{i=1}^{n-1}y_i}{3}\rfloor$ 。

则，$x$ 的取值方案数仅与 $\lfloor \frac{m-\sum_{i=1}^{n-1}y_i}{3}\rfloor$ 有关。

接下来考虑当 $\sum_{i=1}^{n-1} x_i =s,x\geq 0$ 时 $x$ 的取值方案数。

我们可以将上面的问题转换为，有 $s$ 个球，要在球之间放$(n-1)-1$ 个挡板（两个挡板可以放在一个间隙里），问方案数。可以这样转换的原因是，两个挡板之间的球数就表示了这个位置所对应的 $x$ 的值。

接下来考虑这个问题如何处理。

有个显然的性质，就是你不管如何插入挡板，挡板数与球数是不变的，挡板数是$(n-1)-1$，即 $n-2$ ，球数是 $s$ 。则这个问题可以将挡板与球看作一类东西，进一步转化为：在 $n-2+s$ 个物品中 ，取出 $n-2$ 个的方案数 。这个问题的答案显然为 $C^{n-2+s}_{n-2}$。

则可以在 $O(1)$ 时间内算出当 $\sum_{i=1}^{n-1} x_i=s$ 时，$x$ 的取值方案数。

则可以用 $O(n)$ 的时间预处理出对于每个 $s$ ，$x$ 的取值方案数，再利用前缀和就可以快速求出对于 $\sum_{i=1}^{n-1} x_i$ 小于某个值时的取值方案数。

还有一个问题有待解决，就是当 $\sum_{i=1}^{n-1} y_i=s$ 时，$y$ 的取值方案数。

因为$1\leq y_i\leq 2$，所以可以把等号两边同时减去 $(n-1)$，令 $y'_i =y_i-1$ ，则式子变成：$\sum_{i=1}^{n-1} y'_i=s-(n-1) , 0\leq y'_i\leq 1$ 。

问题就转换为了，有 $n-1$ 个球，要选择 $s-(n-1)$ 个的方案数，答案就等于 $C^{n-1}_{s-(n-1)}$ 。

接下来的问题就转换为，枚举 $y_i$ 的和 $s$ ，将 $C^{n-1}_{s-(n-1)} \times \sum_{i=0}^{\lfloor \frac{m-s}{3}\rfloor} C^{n-2+i}_{n-2}$  计入答案，而后半部分可以用前缀和优化。

综上所述，我们得到了一个 $O(n)$ 的做法。

正在渲染内容...