← 返回题目列表

Codeforces · 1930/I

I. 计数很有趣

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

给你一个二进制$$$^\dagger$$$ 模式$$$p$$$,长度为$$$n$$$。

如果对于每个 $$$i$$$ ($$$1 \leq i \leq n$$$),存在索引 $$$l$$$ 和 $$$r$$$ ,则相同长度 $$$n$$$ 的二进制字符串 $$$q$$$ 被称为良好,这样:

- $$$1 \leq l \leq i \leq r \leq n$$$,以及
- $$$p_i$$$ 是字符串 $$$q_lq_{l+1}\ldots q_r$$$ 的众数 $$$^\ddagger$$$。

计算以 $$$998\,244\,353$$$ 为模的良好二进制字符串的数量。

$$$^\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}$$$。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 二进制字符串 $$$p$$$ 的长度。

输入的第二行包含一个二进制字符串 $$$p$$$,长度为 $$$n$$$,由字符 0 和 1 组成。

输出

输出对 $$$998\,244\,353$$$ 取模的好字符串的数量。

示例

输入 #1

1
0

输出 #1

1

输入 #2

3
111

输出 #2

5

输入 #3

4
1011

输出 #3

9

输入#4

6
110001

输出#4

36

输入 #5

12
111010001111

输出 #5

2441

注意

在第二个示例中,好的字符串是

- $$$\mathtt{010}$$$;
- $$$\mathtt{011}$$$;
- $$$\mathtt{101}$$$;
- $$$\mathtt{110}$$$;
- $$$\mathtt{111}$$$。