← 返回题目列表

Codeforces · 1930/D2

D2. 所有子串的总和(困难版)

中文机器翻译题面 查看原题

这是问题的困难版本。两个版本之间的唯一区别是对 $$$t$$$ 和 $$$n$$$ 的约束。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

对于二进制 $$$^\dagger$$$ 模式 $$$p$$$ 和二进制字符串 $$$q$$$,长度均为 $$$m$$$,$$$q$$$ 称为 $$$p$$$ - 好,如果对于每个 $$$i$$$ ($$$1 \leq i \leq m$$$),存在索引 $$$l$$$ 和$$$r$$$ 这样:

- $$$1 \leq l \leq i \leq r \leq m$$$,以及
- $$$p_i$$$ 是字符串 $$$q_l q_{l+1} \ldots q_{r}$$$ 的模式$$$^\ddagger$$$。

对于模式 $$$p$$$,令 $$$f(p)$$$ 为 $$$p$$$-good 二进制字符串(与模式长度相同)中 $$$\mathtt{1}$$$ 的最小可能数量。

给你一个大小为 $$$n$$$ 的二进制字符串 $$$s$$$。求 $$$$$$\sum_{i=1}^{n} \sum_{j=i}^{n} f(s_i s_{i+1} \ldots s_j)。$$$$$$ 换句话说,您需要对 $$$s$$$ 的所有 $$$\frac{n(n+1)}{2}$$$ 子串上 $$$f$$$ 的值求和。

$$$^\dagger$$$ 二进制模式是仅由字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 组成的字符串。

$$$^\ddagger$$$ 字符 $$$c$$$ 是长度为 $$$m$$$ 的字符串 $$$t$$$ 的模式,如果 $$$c$$$ 在 $$$t$$$ 中出现的次数至少为 $$$\lceil \frac{m}{2} \rceil$$$。例如,$$$\mathtt{0}$$$ 是 $$$\mathtt{010}$$$ 的众数,$$$\mathtt{1}$$$ 不是 $$$\mathtt{010}$$$ 的众数,而 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 都是 $$$\mathtt{1}$$$ 的众数$$$\mathtt{011010}$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 二进制字符串 $$$s$$$ 的长度。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$,仅由字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 组成。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,输出 $$$f$$$ 在 $$$s$$$ 的所有子字符串上的值之和。

示例

输入 #1

4
1
1
2
10
5
00000
20
11110110000000111111

输出 #1

1
2
0
346

注意

在第一个测试用例中,唯一的 $$$\mathtt{1}$$$ 好字符串是 $$$\mathtt{1}$$$。因此,$$$f(\mathtt{1})=1$$$。

在第二个测试用例中,$$$f(\mathtt{10})=1$$$ 因为 $$$\mathtt{01}$$$ 是 $$$\mathtt{10}$$$-good,而 $$$\mathtt{00}$$$ 不是 $$$\mathtt{10}$$$-good。因此,答案是 $$$f(\mathtt{1})+f(\mathtt{10})+f(\mathtt{0}) = 1 + 1 + 0 = 2$$$。

在第三个测试用例中,对于所有 $$$1 \leq i \leq j \leq 5$$$,$$$f$$$ 等于 $$$0$$$。因此,答案是$$$0$$$。