P8989 [Peking University Training 2021] Random Walk.

CTT2021 D2T3.

Given a directed graph with $n$ vertices labeled $1,2,\dots,n$. Initially, for all $\forall i\in\{1,2,\dots,n-1\}$, there is a directed edge from $i$ to $i+1$. You may add $m$ more directed edges (any start and end vertices are allowed). Multiple edges and self-loops are allowed. Player A starts from vertex $1$ and moves as a random walk until reaching vertex $n$. You want to maximize the expected number of steps for Player A to move from $1$ to $n$. A random walk is defined as follows: suppose Player A is currently at vertex $x$, and $x$ has $d$ outgoing edges. Then Player A chooses one of these $d$ outgoing edges uniformly at random and moves along it.

The first line contains a positive integer $T$, the number of test cases. It is guaranteed that $T \le 10^5$. The next $T$ lines each contain three integers $n,m,p$, representing the number of vertices in the directed graph, the number of edges you add, and the modulus for the answer. It is guaranteed that $1 \leq n \leq 10^9$, $0 \leq m \leq 10^{18}$, $2\leq p\leq 10^9+7$, and $p$ is a prime.

Output $T$ lines. The $i$-th line contains an integer $ans$, meaning the maximum expected number of steps in the $i$-th test case modulo $p$. (It can be proven that the answer is a rational number. Suppose its simplest form is $\frac{a}{b}$. Then you need to output an $ans$ such that $ans \cdot b \bmod p = a$. It is guaranteed that such an $ans$ exists.)

| Test Package ID | $n\le$ | $m\le$ | $T\le$ | Special Property | Score | | :-------------: | :----: | :-------: | :----: | :--------------: | :---: | | $1$ | $5$ | $5$ | $10$ | None | $10$ | | $2$ | $5$ | $10^2$ | $10$ | None | $10$ | | $3$ | $10^8$ | $10^2$ | $10^2$ | None | $20$ | | $4$ | $50$ | $3,000$ | $3$ | None | $20$ | | $5$ | $10^9$ | $10^9$ | $10^5$ | $m