两个版本的问题唯一的区别是简易版没有更新。
圆桌的边缘上放置了 $$$n$$$ 线轴。线轴有两种类型的线:第一种线是黑色,第二种线是白色。
对于任何两个相同颜色的线轴,您可以用该颜色的线将它们连接在一条直线段上。将匹配定义为将线轴连接在一起的一种方式,以便每个线轴恰好连接到另一个线轴。
着色是为线轴分配颜色(白色和黑色)。如果一种颜色至少有一个匹配,则该颜色被称为有效。也就是说,如果黑色线轴的数量和白色线轴的数量都是偶数。
给定一个匹配,我们可以找到一些白线与一些黑线相交的次数。我们计算相交的不同颜色线对的数量,而不是相交点的数量,因此如果不同对的线在同一点相交,一个相交点可能会被多次计数。如果 $$$c$$$ 是有效的着色,则令 $$$f(c)$$$ 表示所有可能匹配中此类交集的最小数量。
上面的圆圈是通过着色 bwbbbwww 来描述的。如图所示匹配线轴后,不同颜色的线之间有一个交叉点。可以证明它是可能的最小值,所以$$$f(\text{bwbbbwww}) = 1$$$。
给你一个字符串$$$s$$$,代表未完成的着色,有黑色、白色和未着色的线轴。如果您可以通过将颜色分配给 $$$s$$$ 的未着色线轴而不更改其他线轴来实现着色,则着色 $$$c$$$ 称为 $$$s$$$-reachable。
着色 $$$c$$$ 在所有有效的、$$$s$$$可达的着色中均匀随机选择。计算 $$$f(c)$$$ 的期望值。您应该通过模 $$$998244353$$$ 找到它。
将有 $$$m$$$ 更新来更改 $$$s$$$ 的一个字符。每次更新后,您应该再次计算 $$$f(c)$$$ 的预期值。
我们可以证明,每个答案都可以写成 $$$\frac{p}{q}$$$ 的形式,其中 $$$p$$$ 和 $$$q$$$ 是互质整数,$$$q\not\equiv 0\pmod{998244353}$$$。模 $$$998244353$$$ 的答案等于 $$$(p\cdot q^{-1})$$$ 模 $$$998244353$$$。
输入
第一行包含两个整数 $$$n$$$, $$$m$$$ ($$$2\le n\le 2\cdot 10^5$$$, $$$n$$$ 是偶数, $$$0\le m\le 2\cdot 10^5$$$) — 分别是假脱机数量和更新数量。
第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$ — 线轴未完成的着色。第 $$$i$$$ 字符将为“w”、“b”或“?”,分别描述第 $$$i$$$ 线轴是否为白色、黑色或无色。
接下来的 $$$m$$$ 行包含一个整数 $$$i$$$ ($$$1 \leq i \leq n$$$) — $$$s$$$ 中要更新的字符位置,以及一个字符 $$$c$$$ ($$$c \in \{\text{w}, \text{b}, \text{?}\}$$$) — 字符的新颜色更新后假脱机$$$i$$$。
保证最初和每次更新后至少存在一个未着色的线轴。
输出
打印 $$$m+1$$$ 行:$$$f(c)$$$ 最初和每次更新后的预期值。所有值均应通过模 $$$998244353$$$ 找到。
示例
输入 #1
8 0 bwbb?www
输出 #1
1
输入 #2
10 3 ???ww?wb?? 4 ? 5 ? 2 w
输出 #2
436731905 218365953 374341633 530317313
输入 #3
4 3 bw?b 1 w 2 b 1 w
输出 #3
0 0 1 1
注意
第一个测试与图像密切对应。着色“?”因为“w”不会创建有效的着色,因为黑色线轴的数量是奇数。那么唯一可到达的有效着色是 'bwbbbwww' 且 $$$f(\text{bwbbbwww}) = 1$$$,因此预期值为 $$$1$$$。
在第二个测试中,每次更新后的字符串为:
1.???w?wb??
2. ??????wb??
3.?w??????wb??
在第三次测试中,每次更新后的字符串为:
1.ww?b
2.wb?b
3.wb?b