[R59E]01序列 - 代码源竞赛平台

时空限制

1S/512M

定义一个 01 字符串的权值为其中 0110 子序列 $^{\dagger}$ 的数量。

现在给定一个长度为 $n$ 的 01 字符串 $S$ ，请你求出 $S$ 的所有连续子串的权值之和。

由于答案可能非常大，请将最终结果对 $998244353$ 取模后输出。

$^{\dagger}$ ：子序列是指从原字符串中删除若干个（可以不删）字符，剩余字符按照原有顺序拼接而成的字符串。例如 0110 是 01010 的子序列，但不是连续子串。

第一行包含一个整数 $n$ ，表示字符串长度。

第二行包含一个长度为 $n$ 、且仅由字符 0 和 1 组成的字符串 $S$ 。

第一行输出一个整数，表示 $S$ 的所有连续子串的权值之和对 $998244353$ 取模后的结果。

5
01100

字符串 01100 的所有连续子串中，只有以下子串包含 0110 子序列：

子串 $S[1 \dots 4] =$ 0110：包含 $1$ 个 0110 子序列。
子串 $S[1 \dots 5] =$ 01100：包含 $2$ 个 0110 子序列（分别为原串中下标为 $\{1, 2, 3, 4\}$ 和 $\{1, 2, 3, 5\}$ 的字符组成的序列）。

其他所有的子串（如 011、1100 等）权值均为 $0$ 。因此，所有子串的权值之和为 $1 + 2 = 3$ 。

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$
$1$	$30$	$2000$
$2$	$70$	$2\times 10^5$

对于 $100\%$ 的数据， $4 \le n \le 2 \times 10 ^5$ ，字符串 $S$ 仅包含字符 0 和 1。