A182175.Yuilice 的环形灯带

提高+/省选-

官方

通过率:0%

时间限制:5.00s

内存限制:256MB

题目描述

Yuilice 准备了一条由 nn 盏灯组成的环形灯带。灯按顺时针顺序编号为 1,2,…,n1,2,\ldots,n,其中 nn 号灯之后是 11 号灯。

用长度为 nn 的字符串 ss 表示灯的限制:

  • 0:这盏灯必须显示颜色 00;
  • 1:这盏灯必须显示颜色 11;
  • ?:这盏灯可以独立选择颜色 00 或颜色 11。

一次补全需要为所有 ? 选择颜色。若环上任意连续三盏灯都不全是同一种颜色,则这次补全合法。这里的连续三盏灯包括跨过末尾的 (n−1,n,1)(n-1,n,1) 和 (n,1,2)(n,1,2)。

接下来有 qq 次修改,每次把一个位置的限制改为 0、1 或 ?。修改保留到后续操作,允许改成与原来相同的字符。请在每次修改后,输出当前限制的合法补全数对 998244353998244353 取模的结果。

两次补全只要有一盏灯的颜色不同,就视为不同。灯的编号固定,旋转后相同的颜色排列不合并计数。

输入格式

第一行包含两个整数 n,qn,q,分别表示灯的数量和修改次数。

第二行包含一个长度为 nn 的字符串 ss,表示各盏灯最初的颜色限制,仅含字符 0、1 和 ?。

接下来 qq 行,每行包含一个整数 pp 和一个字符 chch,表示将编号为 pp 的灯的限制改为 chch;chch 为 0、1 或 ?。

输出格式

输出 qq 行,第 ii 行一个整数,表示第 ii 次修改后合法补全数对 998244353998244353 取模的结果。

输入输出样例

  • 输入#1

    4 4
    ????
    1 0
    3 0
    2 0
    1 ?
    

    输出#1

    3
    1
    0
    1
    

说明/提示

样例解释

第一次修改后,合法补全为 0011、0101 和 0110,共 33 种。

第二次修改后只有 0101 合法。第三次修改使前三盏灯均为颜色 00,没有合法补全。

第四次修改后只有 1001 合法。

数据范围

对于所有测试数据,满足 3≤n≤1053\le n\le10^5,1≤q≤1051\le q\le10^5,1≤p≤n1\le p\le n,ss 与 chch 仅含字符 0、1 和 ?。

测试点编号 nn qq
1∼41\sim4 3≤n≤183\le n\le18 1≤q≤201\le q\le20
5∼105\sim10 3≤n≤20003\le n\le2000 1≤q≤20001\le q\le2000
11∼2011\sim20 3≤n≤1053\le n\le10^5 1≤q≤1051\le q\le10^5

输入解题思路,AI测评打分。不知道怎么写?

首页