← 返回题目列表

AtCoder · arc170_e

E. BDFS搜索

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

分数: 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 ,按照顶点号升序处理:

      1. 有概率 \frac{P}{100},添加 (x,d+1) 到 前面 of Q.
      2. 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}.