分数: 800 点
问题陈述
给你整数 N 和 P.
有一个图表 N 顶点和 N 边,其中每个顶点都被标记 1 to N。的 i第一条边连接顶点 i 和 i+1 双向。这里,顶点 N+1 指顶点 1.
执行以下算法获得序列 D=(D_1,D_2,\ldots,D_N) 长度 N:
-
设置整数序列 D 长度 N to D=(D_1,\ldots,D_N)=(-1,\ldots,-1)。另外,设置一个顺序 Q 的数字对 Q=((1,0))。同时重复以下过程 Q 不为空:
- 让 (v,d) 是第一个元素 Q。删除该元素。
-
If D_v = -1,然后设置 D_v := d,并且对于每个顶点 x 与顶点相邻 v 这样 D_x=-1,执行以下过程。如果有多个这样的 满足条件的 x ,按照顶点号升序处理:
- 有概率 \frac{P}{100},添加 (x,d+1) 到 前面 of Q.
- If (x,d+1) 未添加到前面 Q,将其添加到 结束 of Q.
求最终序列元素之和的期望值 D 获得,模数 998244353.
解决每个问题 T 给出的测试用例。
期望值的定义 \text{mod } 998244353
可以证明,要找到的期望值总是有理数。 此外,这个问题的约束保证如果该值表示为不可约分数 \frac{P}{Q},那么 Q 不能被整除 998244353。 这里有一个唯一的整数 R 之间 0 和 998244352,包含在内,这样 R\times Q \equiv P\pmod{998244353}。提供这个 R 作为答案。约束
- 1 \leq T \leq 10^4
- 3 \leq N \leq 10^{18}
- 1\leq P \leq 99
- 所有输入数字均为整数。
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
每个案例均按以下格式给出:
N P
输出
打印 您选择的 T 行。的 i第行 (1 \leq i \leq T) 应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
3 3 50 4 1 1000000000000000000 70
示例输出 1
499122179 595552585 760296751
在第一个测试用例中,算法可以按如下方式运行:
- 最初, D=(-1,-1,-1) 和 Q=((1,0))。删除第一个元素 (1,0) 来自 Q.
- D_1 = -1,所以设置 D_1 := 0。顶点 x 与顶点相邻 1 这样 D_x= -1 是 2 和 3.
- 添加 (2,1) 到前面 Q。添加 (3,1) 到结束 Q。现在 Q=((2,1),(3,1)).
- 删除第一个元素 (2,1) 来自 Q.
- D_2 = -1,所以设置 D_2 := 1。顶点 x 与顶点相邻 2 这样 D_x= -1 is 3.
- 添加 (3,2) 到前面 Q。现在 Q=((3,2),(3,1)).
- 删除第一个元素 (3,2) 来自 Q.
- D_3 = -1,所以设置 D_3 := 2。没有顶点 x 与顶点相邻 3 这样 D_x= -1,所以什么也不做。
- 删除第一个元素 (3,1) 来自 Q.
- D_3 =2,所以什么也不做。
- Q 现在为空,因此该过程结束。
在这种情况下,最终获得的序列是 D=(0,1,2)。该算法按上述方式运行的概率为 \frac{1}{8},以及元素的预期总和 D is \frac{5}{2}.