AT_ABC276G Count Sequences 题解
题意
给定 $N, M$，求有多少个长为 $N$ 的非负整数数列 $A = (a_1, a_2, \cdots, a_N)$ 满足：
-
单调不降；
-
$a_N \le M$；
-
相邻两项对 $3$ 不同余。
题解
感觉比较有意思和巧妙的一道题。学习自 官方题解。
首先，将 $A$ 差分得到 $B = (a_1, a_2-a_1, a_3-a_2,\cdots, a_N-a_{N-1})$。$A$ 与 $B$ 构成双射，故对合法的 $B$ 计数，即可知合法的 $A$ 的数目。
因为 $A$ 单调不降且相邻两项对 $3$ 不同余，所以 $B$ 为非负整数数列，且从第 $2$ 项开始模 $3$ 余 $1$ 或余 $2$。又因为 $a_N \le M$，所以 $\sum b \le M$。
问题即转化为求从第二项开始每项模 $3$ 余 $1$ 或余 $2$，且和不超过 $M$ 的非负整数数列的数目。
将 $B$ 的每一项写成带余除法的形式：$b_i = 3k_i + r_i$，这里 $1 \le i \le N,\ k_i \in \mathbb N,\ r_i \in {0, 1, 2}$。并记 $K = (k_1, k_2, \cdots, k_N),\ R = (r_1, r_2, \cdots, r_N)$。
考察一个特定的 $R$，则合法的 $K$ 的数目，即为满足长度为 $N$ 且和不超过 $\left\lfloor\frac{M - \sum r}{3}\right\rfloor$ 的非负整数数列的数目。求满足长度为 $N$ 且和等于 $S$ 的非负整数数列数目是经典问题，由隔板法可知答案是 $\binom{S + N - 1}{N - 1}$。对其做前缀和，即得满足长度为 $N$ 且和不超过一给定值的非负整数数列数目。
由上面可知，$R$ 对 $K$ 的影响只来源于 $\sum r$。枚举 $r_1$，枚举 $r_2 \sim r_N$ 中取值为 $1$ 的个数 $c$，容易求出具体排列的方案数 $\binom{N - 1}{c}$，同时容易求出 $\sum r = r_1 + 2N - c - 2$，从而得到对应合法 $K$ 的数目。由此可以求出答案。