#P11485. [2023省队模拟]游戏

    ID: 10633 传统题 6000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-双射计数容斥原理计数 DP阶乘逆元预处理卷积转化分治 FFTNTT

[2023省队模拟]游戏

题目描述

当九分裤宝宝到达爆炸现场时,公民们已经吵了起来,有鼠甚至直接动起了手,整个一片鼠头攒动的景象。

但是九分裤宝宝注意到,在远处有一位公民,正不屑地、恶狠狠地盯着他,显然是看出了九分裤宝宝就是这件事情的始作俑者。

九分裤宝宝恼羞成怒,冲上去想要对他拳打脚踢,可这位公民直接打开地下的门钻了进去。

九分裤宝宝冲了上来,发现门上有这样一个游戏:

门上显示着一个长度为 nn 的、仅由 00 和 11 以及 ?? 三种字符组成的字符串 SS ,和 n+1n + 1 个待填充的方框。设填充后第 ii 个方框内的字符串为 TiT_i (从 00 开始编号),它们需要满足以下要求:

• T0T_0 为空串。 • Ti+1T_{i+1} 是在 TiT_i 的基础上填入一个 00 或 11 得到的。 • TnT_n 必须和 SS 模糊匹配,也即对于 TnT_n 和 SS 中的每一组对应的字符,要么二者完全一致,要么存在 ?? 字符。

九分裤宝宝心想:“这不白给吗。” 于是很快解出了这个游戏。结果,打开的门下又有另外一道门,要求在 1010 秒钟之内算出刚才的游戏的不同方案数对质数 998244353998244353 取模的结果,两种方案不同当且仅当存在 i∈[0,n]i \in [0, n] ,满足两种方案中的 TiT_i 不完全相同。

这下九分裤宝宝没辙了,随便蒙了一个答案,然而并没有正确,最后他被门上预留的炸弹给炸飞了。

门下的那位公民钻了出来,告诉了大家真相,大家为他惩治了坏蛋而欢呼,就在这时,一位小朋友突然指着他说:“这不是神话里智勇双全的 qiulyqiuly 警长吗?”

大家惊奇地发现,这确实是 CCFCCF 行星盛传的神话里的 qiulyqiuly 警长。就在大家想要上去要签名、合影的时候, pcqpcq 扔下的水到达了地表 ——

一代传奇就这样被毁灭了,和世人以及整个世界一起。

然而 pcqpcq 早就注意到了第二道门上的有趣的题目,他很想求出其答案。

输入格式

第一行输入一个整数 nn 。

第二行输入一个长度为 nn 的字符串 SS 。

输出格式

输出一行一个整数,表示答案。

数据范围

对于 100%100\% 的数据,有 1≤n≤5×1051 \le n \le 5 \times 10^5 。

保证 SS 仅由 00 、 11 和 ?? 三种字符组成。

子任务编号 n≤n \le 特殊性质
11 1010 无
22 5×1055 \times 10^5 AA
33 BB
44 50005000 无
55 2×1052 \times 10^5
66 5×1055 \times 10^5

特殊性质 AA : SS 仅由 ?? 字符组成。 特殊性质 BB : SS 中 00 和 11 两种字符总共最多出现 1010 次。

输入样例 1

3
01?

输出样例 1

8

输入样例 2

9
0??001011

输出样例 2

32400

输入样例 3

40
1111111111111111111100000000000000000000

输出样例 3

88808106

样例解释

样例 11 中,满足条件的方案有以下 88 种:

T0T_0 为空串, T1=0,T2=00,T3=010T_1 = 0, T_2 = 00, T_3 = 010 ; T0T_0 为空串, T1=0,T2=01,T3=010T_1 = 0, T_2 = 01, T_3 = 010 ; T0T_0 为空串, T1=0,T2=01,T3=011T_1 = 0, T_2 = 01, T_3 = 011 ; T0T_0 为空串, T1=0,T2=10,T3=010T_1 = 0, T_2 = 10, T_3 = 010 ; T0T_0 为空串, T1=1,T2=01,T3=010T_1 = 1, T_2 = 01, T_3 = 010 ; T0T_0 为空串, T1=1,T2=01,T3=011T_1 = 1, T_2 = 01, T_3 = 011 ; T0T_0 为空串, T1=1,T2=10,T3=010T_1 = 1, T_2 = 10, T_3 = 010 ; T0T_0 为空串, T1=1,T2=11,T3=011T_1 = 1, T_2 = 11, T_3 = 011 。