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