CF1930D 题解

escapist404 · 2024-02-18 01:46:49 · 题解

对两个长度为 m 的 01 串 p, q，我们称 q 是 p - 好的，当且仅当对每个 1 \le i \le m 都存在 1 \le l \le i \le r \le m 使得字符 p_i 在子串 q_l q_{l+1} \cdots q_r 里出现次数不少于长度的一半，即 p_i 是子串的非严格众数。

对 01 串 p，定义 f(p) 是所有 p - 好的 01 串中，包含字符 1 个数最少的串的 1 个数。

现在给定长度为 n 的 01 串 s，求所有子串的 f 函数的和，即：

坑。