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 翻译