A182175.Yuilice 的环形灯带
提高+/省选-
官方
通过率:0%
时间限制:5.00s
内存限制:256MB
题目描述
Yuilice 准备了一条由 n 盏灯组成的环形灯带。灯按顺时针顺序编号为 1,2,…,n,其中 n 号灯之后是 1 号灯。
用长度为 n 的字符串 s 表示灯的限制:
0:这盏灯必须显示颜色 0;1:这盏灯必须显示颜色 1;?:这盏灯可以独立选择颜色 0 或颜色 1。
一次补全需要为所有 ? 选择颜色。若环上任意连续三盏灯都不全是同一种颜色,则这次补全合法。这里的连续三盏灯包括跨过末尾的 (n−1,n,1) 和 (n,1,2)。
接下来有 q 次修改,每次把一个位置的限制改为 0、1 或 ?。修改保留到后续操作,允许改成与原来相同的字符。请在每次修改后,输出当前限制的合法补全数对 998244353 取模的结果。
两次补全只要有一盏灯的颜色不同,就视为不同。灯的编号固定,旋转后相同的颜色排列不合并计数。
输入格式
第一行包含两个整数 n,q,分别表示灯的数量和修改次数。
第二行包含一个长度为 n 的字符串 s,表示各盏灯最初的颜色限制,仅含字符 0、1 和 ?。
接下来 q 行,每行包含一个整数 p 和一个字符 ch,表示将编号为 p 的灯的限制改为 ch;ch 为 0、1 或 ?。
输出格式
输出 q 行,第 i 行一个整数,表示第 i 次修改后合法补全数对 998244353 取模的结果。
输入输出样例
输入#1
4 4 ???? 1 0 3 0 2 0 1 ?
输出#1
3 1 0 1
说明/提示
样例解释
第一次修改后,合法补全为 0011、0101 和 0110,共 3 种。
第二次修改后只有 0101 合法。第三次修改使前三盏灯均为颜色 0,没有合法补全。
第四次修改后只有 1001 合法。
数据范围
对于所有测试数据,满足 3≤n≤105,1≤q≤105,1≤p≤n,s 与 ch 仅含字符 0、1 和 ?。
| 测试点编号 | n | q |
|---|---|---|
| 1∼4 | 3≤n≤18 | 1≤q≤20 |
| 5∼10 | 3≤n≤2000 | 1≤q≤2000 |
| 11∼20 | 3≤n≤105 | 1≤q≤105 |
输入解题思路,AI测评打分。不知道怎么写?