#CW14. 计数(count)

计数(count)

题目描述

给定一个长度为 nn 的二进制字符串 ss。

可以进行任意次(包括 00 次)以下操作:

  • 选择两个下标 l,rl, r,满足 1≤l≤r≤n1 \le l \le r \le n 且 sl=srs_l = s_r;
  • 将子串 slsl+1…srs_l s_{l+1} \ldots s_r 翻转。

求通过上述操作能够得到的不同二进制字符串数量,答案对 998244353998244353 取模。

子串翻转是指将 slsl+1…srs_l s_{l+1} \ldots s_r 替换为 srsr−1…sls_r s_{r-1} \ldots s_l。

例如,如果 s=00110s=00110,可以选择 l=1l=1 和 r=5r=5,因为 s1=s5=0s_1=s_5=0。执行操作后,字符串变成 0110001100。

输入格式

第一行包含一个整数 nn,表示字符串长度。

第二行包含一个长度为 nn 的二进制字符串 ss。

输出格式

输出一行一个整数,表示结果对 998244353998244353 取模后的值。

样例 1 输入

6
001010

样例 1 输出

3

样例 1 解释

在这个样例中,恰好能获得如下三个字符串:

  • 001010
  • 010010
  • 010100

数据范围

对于所有测试数据,保证:1≤n≤1061 \le n \le 10^6。

测试点 n≤n \le 特殊性质
1∼41 \sim 4 88 无
5∼65 \sim 6 2020
7∼87 \sim 8 10001000
9∼119 \sim 11 10610^6 存在 i≤ji \le j,使得 [i,j][i,j] 内全为 11,区间外全为 00
12∼1412 \sim 14 不存在两个相邻的 11
15∼2015 \sim 20 无