#2057. 随机游走

    ID: 2057 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest870来源:qoj.ac数据:公开样例线性代数

随机游走

随机游走

题目描述

标题: 随机游走 - Problem - QOJ.ac

Statistics

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