[北大集训 2021] 随机游走

Luogu

IDLGP8989

Time1000ms

Memory1024MB

DifficultyP6

2021O2优化CTT（清华集训/北大集训）

给定一张 $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$ 条出边中**等概率**随机选择一条走过去。 ## Input 输入的第一行包含一个正整数 $T$，表示数据组数，保证 $T \le 10^5$。接下来 $T$ 行，每行包含三个整数 $n,m,p$，分别表示有向图的点数、你添加的边数以及答案的模数，保证 $1 \leq n \leq 10^9$，$0 \leq m \leq 10^{18}$，$2\leq p\leq 10^9+7$ 且 $p$ 是质数。 ## Output 输出 $T$ 行，第 $i$ 行一个整数 $ans$ 表示第 $i$ 组数据中最大的期望步数对 $p$ 取模后的值（可以证明答案是有理数，设其用最简分数表示为 $\frac{a}{b}$，则你需要满足 $ans \cdot b \bmod p=a$，保证这样的 $ans$ 存在）。 [samples] ## Background CTT2021 D2T3 ## Note | 测试包编号 | $n\le$ | $m\le$ | $T\le$ | 特殊性质 | 分数 | | :--------: | :----: | :-------: | :----: | :------: | :--: | | $1$ | $5$ | $5$ | $10$ | 无 | $10$ | | $2$ | $5$ | $10^2$ | $10$ | 无 | $10 $ | | $3$ | $10^8$ | $10^2$ | $10^2$ | 无 | $20$ | | $4$ | $50$ | $3,000$ | $3$ | 无 | $20 $ | | $5$ | $10^9$ | $10^9$ | $10^5$ | $m<n-1$ | $10$ | | $6$ | $10^9$ | $10^{18}$ | $10^5$ | 无 | $30$ |

Samples

Input #1

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

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[北大集训 2021] 随机游走",
    "description": {
      "content": "给定一张 $n$ 个点的有向图，点标号为 $1,2,\\dots,n$，初始时对 $\\forall i\\in\\{1,2,\\dots,n-1\\}$，从 $i$ 到 $i+1$ 有一条有向边。 你可以在其中再加入 $m$ 条有向边（起点终点任意），允许有重边和自环。 小 A 会从 $1$ 出发，以随机游走的形式行动，直到抵达 $n$。你希望最大化小 A 从 $1$ 移动到 $n$ 的期望步数。 定",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8989"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一张 $n$ 个点的有向图，点标号为 $1,2,\\dots,n$，初始时对 $\\forall i\\in\\{1,2,\\dots,n-1\\}$，从 $i$ 到 $i+1$ 有一条有向边。\n\n你可以在其中再加入 $m$ 条有向边（起点终点任意），允许有重边和自环。\n\n小 A 会从 $1$ 出发，以随机游走的形式行动，直到抵达 $n$。你希望最大化小 A 从 $1$ 移动到 $n$ 的期望步数。\n\n定...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments