409973: GYM103870 R Rock Paper Scissors (Hard Version)

This is the hard version. The difference between the easy and the hard versions is that the hard version has higher constraints.

Misaka Imouto $$$1$$$, Misaka Imouto $$$2$$$, ..., and Misaka Imouto $$$n$$$ are all playing rock paper scissors to determine who should go buy the cake. Since they are all connected to the same network, let's assume that all Misaka Imouto's act the same.

A game of rock paper scissors is dictated as follows:

1. If there is $$$1$$$ person, the game ends immediately (taking $$$0$$$ rounds).
2. Otherwise, each Misaka Imouto throws out a choice between rock, paper, and scissors with exactly $$$\frac{1}{3}$$$ probability. All choices are independent of each other.
3. If all options of rock, paper, and scissors are present, then the game is a tie and no one steps out of the game. If only one option is present, the game is a tie and no one steps out of the game. However, if only two options are present, then the winners and the losers are well defined, and the losers step out of the game. All people who are still in the game repeat step 1 for a new round.

One possible game between $$$3$$$ Misaka Imouto's could be as follows: RPS, RRS, SSX, SRX, and ending with the second Misaka winning after $$$4$$$ rounds. In this game, R means rock, S means scissors, P means paper, and X means that this Misaka Imouto has lost already and was not allowed to play.

For each $$$i$$$ from $$$1$$$ to $$$n$$$, find the expected number of rounds a game with $$$i$$$ Misaka Imoutos initially lasts.

The input contains two numbers $$$n$$$ and $$$P$$$, $$$(2 \leq n \leq 10^5, 10^{8} \leq P \leq 10^{9})$$$. It is guaranteed that $$$P$$$ is a prime.

Output $$$n$$$ integers, the $$$i$$$'th integer denoting the expected number of rounds a game with $$$i$$$ Misakas initially will last.

So for each $$$i$$$ from $$$1$$$ to $$$n$$$, let the final expected number of rounds of a game with $$$i$$$ Misaka Imoutos be $$$\frac{x_i}{y_i}$$$, output $$$z_i$$$ $$$(0 \leq z_i < P)$$$ where $$$x_i \equiv y_i \cdot z_i \pmod P$$$.

5 100000007

0 50000005 25000004 64285722 25714292 

$$$50000005$$$ is also $$$\frac{3}{2} \mod 100000007$$$

$$$25000004$$$ is also $$$\frac{9}{4} \mod 100000007$$$

—

Idea: 3366

Preparation: 3366

Occurrences: Advanced 11