【北大集训2021】随机游走 - 题目

给定一张 $n$ 个点的有向图，点标号为 $1, 2, \dots, n$ ，初始时对 $\forall i \in {1, 2, \dots, n - 1}$ ，从 $i$ 到 $i + 1$ 有一条有向边。

你可以在其中再加入 $m$ 条有向边（起点终点任意），允许有重边和自环。

小 A 会从 $1$ 出发，以随机游走的形式行动，直到抵达 $n$ 。你希望最大化小A从 $1$ 移动到 $n$ 的期望步数。

定义随机游走是这样的一种移动方式：设小 A 当前在点 $x$ ， $x$ 有 $d$ 条出边，则小 A 会从这 $d$ 条出边中等概率随机选择一条走过去。

从标准输入读入数据。

输入的第一行包含一个正整数 $T$ ，表示数据组数。

接下来 $T$ 行，每行包含三个整数 $n, m, p$ ，分别表示有向图的点数、你添加的边数以及答案的模数。

输出到标准输出。

输出 $T$ 行，第 $i$ 行一个整数 $a n s$ 表示第 $i$ 组数据中最大的期望步数对 $p$ 取模后的值（可以证明答案是有理数，设其用最简分数表示为 $\frac{a}{b}$ ，则你需要满足 $a n s \cdot b mod p = a$ ，保证这样的 $a n s$ 存在）。

4
3 2 97
10 25 233
6 12345 2333
1000000000 1000000000000000000 1000000007

测试包编号	$n \leq$	$m \leq$	$T \leq$	特殊性质	分数
$1$	$5$	$5$	$10$	无	$10$
$2$	$5$	$10^{2}$	$10$	无	$10$
$3$	$10^{8}$	$10^{2}$	$10^{2}$	无	$20$
$4$	$50$	$3000$	$3$	无	$20$
$5$	$10^{9}$	$10^{9}$	$10^{5}$	$m < n - 1$	$10$
$6$	$10^{9}$	$10^{18}$	$10^{5}$	无	30

对于所有数据，保证 $T \leq 10^{5}, 1 \leq n \leq 10^{9}, 0 \leq m \leq 10^{18}, 2 \leq p \leq 10^{9} + 7$ 且 $p$ 是质数。

时间限制： $1s$

空间限制： $1GB$

Universal Online Judge