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

TLE_Automat · 2025-04-01 15:29:43 · 题解

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

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

第一种就是直接计算 g_m。
第二种是考虑 h_i = \sum\limits_{j \ge i} g_j 是否好算，然后用 h_m - h_{m + 1} 就是答案。
第三种是考虑 f_i = \sum\limits_{j \le i}^{}\binom{i}{j}g_{j} 或者 f_i = \sum\limits_{j \ge i}\binom{j}{i}g_{j} 是否好算，然后用二项式反演求出 g_m。

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

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

10^{n - 4i}\operatorname{calc}(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} 次。

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

f_i = \sum\limits_{j = i}^{M}\binom{j}{i}g_{j} = 10^{n - 4i}\operatorname{calc}(n - 4i, i + 1)

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

g_m = \sum\limits_{i = m}^{M} (-1)^{i - m}\binom{i}{m}f(i)

时间复杂度 O(n)。