#2057. 随机游走
随机游走
随机游走
题目描述
标题: 随机游走 - Problem - QOJ.ac
The problem was used in the following contests:
给定一张 n 个点的有向图,点标号为 1,2,…,n,初始时对 ∀i∈{1,2,…,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 行一个整数 ans 表示第 i 组数据中最大的期望步数对 p 取模后的值(可以证明答案是有理数,设其用最简分数表示为 ab,则你需要满足 ans⋅bmodp=a,保证这样的 ans 存在)。
样例数据
样例输入
4
3 2 97
10 25 233
6 12345 2333
1000000000 1000000000000000000 1000000007
样例输出
6
131
1206
161905971
数据范围与提示
测试包编号 n≤ m≤ T≤ 特殊性质 分数 1 5 5 10 无 10 2 102 10 3 108 102 20 4 50 3000 3 20 5 109 109 105 m<n−1 10 6 1018 无 30
对于所有数据,保证 T≤105,1≤n≤109,0≤m≤1018,2≤p≤109+7 且 p 是质数。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4
3 2 97
10 25 233
6 12345 2333
1000000000 1000000000000000000 1000000007
6
131
1206
161905971