← 返回题目列表

Codeforces · 1450/H1

H1. 多线程(简易版)

中文机器翻译题面 查看原题

两个版本的问题唯一的区别是简易版没有更新。

圆桌的边缘上放置着 $$$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}$$$。