AT_arc170_e.[ARC170E] BDFS

给定整数 $N, P$。

有一个 $N$ 个顶点 $N$ 条边的图，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $i$ 和顶点 $i+1$，是双向的。这里顶点 $N+1$ 代表顶点 $1$。

请执行以下算法，得到一个长度为 $N$ 的数列 $D=(D_1, D_2, \ldots, D_N)$。

• 令长度为 $N$ 的整数列 $D = (D_1, \ldots, D_N) = (-1, \ldots, -1)$。同时，令数对序列 $Q = ((1, 0))$。只要 $Q$ 非空，重复以下操作：

  • 取出 $Q$ 的首元素 $(v, d)$，并将其从 $Q$ 中删除。
  • 如果 $D_v = -1$，则令 $D_v := d$，并对与顶点 $v$ 相邻且满足 $D_x = -1$ 的每个顶点 $x$，按顶点编号从小到大依次进行如下操作：
    1. 以概率 $\frac{P}{100}$，将 $(x, d+1)$ 加入 $Q$ 的首部。
    2. 若未将 $(x, d+1)$ 加入 $Q$ 的首部，则将其加入 $Q$ 的尾部。

最终得到的 $D$ 的所有元素之和的期望值，模 $998244353$ 后输出。

给定 $T$ 组测试数据，请分别输出每组的答案。

期望值 $\bmod\ 998244353$ 的定义：可以证明，所求期望值一定是有理数。在本题的约束下，若将其表示为最简分数 $\frac{P}{Q}$，则 $Q$ 保证不被 $998244353$ 整除。此时，唯一存在一个 $0$ 到 $998244352$ 之间的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$。请输出这个 $R$ 作为答案。

输入按以下格式从标准输入给出。

$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$

每组数据格式如下：

$N\ P$

输出 $T$ 行，第 $i$ 行输出第 $i$ 组测试数据的答案。

数据范围

• $1 \leq T \leq 10^4$
• $3 \leq N \leq 10^{18}$
• $1 \leq P \leq 99$
• 输入的所有数均为整数

样例解释 1

对于第 $1$ 组测试数据，算法的执行过程例如如下：

• 初始时，$D = (-1, -1, -1),\ Q = ((1, 0))$。取出 $Q$ 首元素 $(1, 0)$。
• 因为 $D_1 = -1$，令 $D_1 := 0$。与顶点 $1$ 相邻且 $D_x = -1$ 的顶点为 $2, 3$。
• 将 $(2, 1)$ 加入 $Q$ 首部，将 $(3, 1)$ 加入 $Q$ 尾部。此时 $Q = ((2, 1), (3, 1))$。
• 取出 $Q$ 首元素 $(2, 1)$。
• 因为 $D_2 = -1$，令 $D_2 := 1$。与顶点 $2$ 相邻且 $D_x = -1$ 的顶点为 $3$。
• 将 $(3, 2)$ 加入 $Q$ 首部。此时 $Q = ((3, 2), (3, 1))$。
• 取出 $Q$ 首元素 $(3, 2)$。
• 因为 $D_3 = -1$，令 $D_3 := 2$。与顶点 $3$ 相邻且 $D_x = -1$ 的顶点不存在，不做任何操作。
• 取出 $Q$ 首元素 $(3, 1)$。
• 因为 $D_3 = 2$，不做任何操作。
• $Q$ 为空，算法结束。

此时最终 $D = (0, 1, 2)$。上述过程发生的概率为 $\frac{1}{8}$，$D$ 的元素和的期望值为 $\frac{5}{2}$。

由 ChatGPT 4.1 翻译