题解：P10986 [蓝桥杯 2023 国 Python A] 2023

令 $g_i$ 代表恰好有 $i$ 个 $2023$ 时的总方案数，$M = \lfloor\frac{n}{4}\rfloor$。

当我们遇到这种“恰好有多少个满足某个条件”的计数时，第一步大致有三种思考方向。

对于此题来说，第一种方法并不好用，考虑第二种和第三种。

如果我们钦定当前至少选 $i$ 个 $2023$，那么我们可以想到一种 naive 的统计方法，先固定这 $i$ 个 $2023$，然后剩下 $n - 4i$ 个 数字插到 $i + 1$ 个空里，每个空允许空，并且这些数字的值随便取，那么我们有

种方案，其中 $\operatorname{calc}(x, y) = \binom{x + y - 1}{y - 1}$。

那么我们现在遇到了一个问题，这个值到底是 $h_i$ 还是 $f_i$ 或者两个都不是。

考虑 $g_j(j \ge i)$ 中的一种方案（即 $2023$ 恰好出现了 $j$ 次的一种方案）， 它在当前 $i$ 的统计中会被重复统计 $\binom{j}{i}$ 次。

考虑这是为什么，因为可以把这 $j$ 个 $2023$ 中的 $i$ 个 $2023$ 看作是一开始就放好的，剩下的数字看作是插进来的，这样每一种都会被统计一次，总共会被重复统计 $\binom{j}{i}$​ 次。

所以这个式子代表的含义就是

使用二项式反演，即可得到

时间复杂度 $O(n)$。