#951. [yLOI2019] 棠梨煎雪
[yLOI2019] 棠梨煎雪
题目描述
扶苏正在听《棠梨煎雪》的时候,
歌词中的主人公与她的朋友一年会有一次互相写信给对方,一共通信了 年。为了简化问题,我们认为她们每封信的内容都是一条二进制码,并且所有二进制码的长度都是 。即每封信的内容都是一个长度为 的字符串,这个字符串只含字符 0 或 1。
这天她拿出了朋友写给她的所有信件,其中第 年的写的信件编号为 。由于信件保存时间过久,上面有一些字符已经模糊不清,我们将这样的位置记为 ?,? 字符可以被解释为 0 或 1。由于她的朋友也是人,符合人类的本质,所以朋友在一段连续的时间中书写的内容可能是相同的。现在她想问问你,对于一段连续的年份区间 中的所有信件,假如朋友在这段时间展示了人类的本质,所写的是同一句话,那么这一句话一共有多少种可能的组成。也即一共有多少字符串 ,满足在这个区间内的所有信件的内容都可能是 。
一个长度为 的只含 0,1,? 的字符串 可能是一个字符串 当且仅当 满足如下条件:
- 的长度也是 。
- 中只含字符
0,1。 - 中所有为
0的位置在 中也是0。 - 中所有为
1的位置在 中也是1。 - 中为
?的位置在 中可以为0也可以是1。
同时她可能会突然发现看错了某年的信的内容,于是她可能会把某一年的信的内容修改为一个别的只含 0,1,? 的长度为 的字符串。
输入格式
每个输入文件中都有且仅有一组测试数据。
输入数据第一行为三个用空格隔开的整数,分别代表代表字符串长度 ,字符串个数 和操作次数 。
下面 行,每行是一个长度为 的字符串,第 行的字符串 代表第 年信的内容。
下面 行,每行的第一个数字是操作编号 。
- 如果 ,那么后面接两个整数 ,代表一次查询操作。
- 如果 ,那么后面接一个整数 ,在一个空格后会有一个长度为 的字符串 ,代表将第 个字符串修改为新的字符串 。
输出格式
为了避免输出过大,请你输出一行一个数代表所有查询的答案异或和对 取异或的结果。
样例
3 3 5
010
0?0
1?0
0 1 2
0 2 3
1 3 0??
0 2 3
0 1 3
2
题目来源:洛谷 P5522