TLE '17 Contest 4 P5 - Pascal's Tree - Olympiads Online Judge

TLE '17 Contest 4 P5 - Pascal's Tree

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

Problem types

The Pascal's-triangle-influenced Christmas Tree.

Fax McClad, Croneria's most decorative bounty hunter, has recently been fascinated with Pascal's triangle. He is in charge of decorating the Cronerian Christmas tree this year, so he does not want to miss an opportunity to reference Pascal's triangle in his design.

He decides to print the first $N$ $N$ rows of Pascal's triangle on ornaments to hang on the tree. Since these numbers can get rather large, he will put the values modulo $M$ $M$ .

Unfortunately, Fax doesn't know what the values of the $N^\text{th}$ $N^{th}$ row of the triangle are, modulo $M$ $M$ . Could you please help him? As a refresher, the $i^\text{th}$ $i^{th}$ value (from $1$ $1$ to $N+1$ $N + 1$ ) of the $N^\text{th}$ $N^{th}$ row of Pascal's triangle is $\dbinom{N}{i-1}$ $(\binom{N}{i - 1})$ .

Constraints

$1 \le N \le 200\,000$ $1 \leq N \leq 200 000$

$2 \le M \le 10^9$ $2 \leq M \leq 10^{9}$

Subtask	Points	Additional Constraints
1	5	$N \le 10$ $N \leq 10$
2	10	$N \le 2000$ $N \leq 2000$
3	20	$M = 10^8+7$ $M = 10^{8} + 7$
4	20	$M$ $M$ is prime
5	45	None

Note: It may be helpful to know that $10^8+7$ $10^{8} + 7$ is prime.

Input Specification

The first line will contain $2$ $2$ integers, $N$ $N$ and $M$ $M$ .

Output Specification

Output $N+1$ $N + 1$ lines. The $i^\text{th}$ $i^{th}$ line should contain a single integer, the value of $\dbinom{N}{i-1} \bmod M$ $(\binom{N}{i - 1}) mod M$ .

Sample Input

Copy

4 6

Sample Output

Copy

Explanation for Sample Output

The $4^\text{th}$ $4^{th}$ line of Pascal's triangle is $1\ 4\ 6\ 4\ 1$ $1 4 6 4 1$ . We calculate each element $\bmod 6$ $mod 6$ to get $1\ 4\ 0\ 4\ 1$ $1 4 0 4 1$ .

Comments

-5

player of stupid games, winner of stupid prizes commented on Nov. 11, 2023, 11:52 p.m.

OMG close call 0.997

This comment is hidden due to too much negative feedback. Show it anyway.