CF1930E. 2..3...4.... Wonderful! Wonderful!

Alex_Wei · 2024-02-25 20:43:15 · 题解

CF1930E. 2..3...4.... Wonderful! Wonderful!

如果一个数被删去，将其标记为 1，否则标记为 0。问题即数 01 串个数。

考虑最后一次操作没有被删去的数，它前面至少有 k 个被删去的数，后面也至少有 k 个被删去的数。

于是 01 串合法的必要条件：

• 存在 0 使得它左侧和右侧至少有 k 个 1。

这个条件充分吗？很明显是充分的：考虑撤回最后一次操作，首先在 0 两侧各选 k - 1 个 1 将它们标记为 0。如果左侧 1 的个数不小于右侧 1 的个数，那么先在右侧选一个 1 标记为 0，此时 1 的个数为奇数，且最中间的 1 在左侧，将其标记为 0​。反之同理。

枚举 k，枚举操作次数 c，考虑用所有方案数 \binom n {2ck} 减去不合法的方案数。根据充要条件，不合法当且仅当除了左右最外侧的 k - 1 个 1 以外，剩下的 1 形成连续段。将这 d = 2ck - 2k + 2 个 1 缩起来，相当于在 n - d + 1 个位置选 2ck - d + 1 个 1，即 \binom {n - 2(c - 1)k - 1} {2k - 1}。

时间复杂度是调和级数的 \mathcal{O}(n\ln n)。代码。