← 返回题目列表

Codeforces · 1781/F

F. 支架插入

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

Vika 喜欢玩括号序列。今天,她想使用以下算法创建一个新的括号序列。最初,Vika 的序列是一个空字符串,然后她将重复以下操作 $$$n$$$ 次:

- 在当前括号序列中选择一个位置,统一随机插入新括号。如果当前序列的长度是$$$k$$$,则有$$$k+1$$$这样的地方:第一个括号之前,第一个和第二个括号之间,$$$\ldots$$$,第$$$k$$$之后。特别是,在空括号序列中有一个这样的位置。
- 以 $$$p$$$ 的概率选择字符串 "()" 或以 $$$1 - p$$$ 的概率选择字符串 ")(" 并将其插入到所选位置。括号序列的长度将增加 $$$2$$$。

如果可以通过在括号序列中插入字符“+”和“1”来获得正确的算术表达式,则该括号序列称为正则括号序列。例如,序列“(())()”、“()”和“(()(()))”是规则的,而“)(”、“(()”和“(()))(”则不是。

Vika 想知道她的括号序列最后是常规序列的概率。帮助她找到这个概率模$$$998\,244\,353$$$(参见输出部分)。

输入

唯一的一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n \le 500$$$; $$$0 \le q \le 10^4$$$)。这里$$$n$$$等于括号插入操作的次数,而Vika在算法的每一步选择字符串“()”的概率等于$$$p = q \cdot 10^{-4}$$$。

输出

打印 Vika 最终括号序列为正则的概率,以 $$$998\,244\,353$$$ 为模。

正式地,令 $$$M = 998\,244\,353$$$。可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。

示例

输入 #1

1 7500

输出 #1

249561089

输入 #2

2 6000

输出 #2

519087064

输入 #3

5 4000

输出 #3

119387743

注意

在第一个例子中,Vika 将以 $$$p = \frac{3}{4}$$$ 的概率得到一个规则的括号序列 (),她将得到一个不规则的括号序列 )( 概率为 $$$1 - p = \frac{1}{4}$$$。寻求的概率是 $$$\frac{3}{4}$$$ 和 $$$249\,561\,089 \cdot 4 \equiv 3 \pmod{998\,244\,353}$$$。

在第二个示例中,寻求的概率是 $$$\frac{11}{25}$$$。