P8329 [ZJOI2022] Tree

The annual ZJOI is about to be held again, but the veteran problem setter Kujou Karen suddenly had an urgent matter and had to return to the UK. “Leave it to you all! There will definitely be no problem desu!”, after saying that, Karen ran off into the distance. Shinobu, Alice, Aya, and Youko watched Karen leave and felt a bit at a loss. After all, there were less than three weeks left until ZJOI. “Since this is the task Karen-chan left behind, we must work hard to finish it. After all, I am the older sister,” said Alice. So everyone began setting problems enthusiastically. “Hopefully this is the first and also the last time,” everyone thought in unison. At the same time, the main character of the problem was set to be Kujou Karen!

Kujou Karen is a girl who likes trees. She wants to generate two trees, each with $n$ nodes. The first tree is generated as follows: 1. Node $1$ is the root of the tree. 2. For $i \in [2, n]$, choose a node from $[1, i - 1]$ as the parent of $i$. The second tree is generated as follows: 1. Node $n$ is the root of the tree. 2. For $i \in [1, n - 1]$, choose a node from $[i + 1, n]$ as the parent of $i$. Kujou Karen wants that for any $i \in [1, n]$: if node $i$ is a leaf in the first tree, then node $i$ is a non-leaf in the second tree; if node $i$ is a non-leaf in the first tree, then node $i$ is a leaf in the second tree. A node is called a leaf if and only if no node has it as its parent. Kujou Karen wants you to count the number of ways to generate the two trees. Specifically, you need to compute the number of ways for all $n \in [2, N]$. Two ways are different if and only if there exists a node $i$ in one of the trees whose parent is different in the two ways. Since the answer may be very large, you only need to output the result modulo $M$.

The first line contains two integers $N, M$, representing the upper limit on the number of nodes in the tree and the modulus.

Output $N - 1$ lines, each containing one integer. Specifically, on the $i$-th line output the value of the answer modulo $M$ when $n = i + 1$.

For all test cases: it is guaranteed that $2 \le N \le 500$ and $10 \le M \le 2^{30}$. The specific limits for each test case are shown in the table below: | Test Case ID | $N \le$ | Special Constraints | |:-:|:-:|:-:| | $1$ | $10$ | None | | $2$ | $20$ | Guaranteed that $M$ is prime | | $3$ | $50$ | None | | $4$ | $50$ | Guaranteed that $M$ is prime | | $5$ | $100$ | None | | $6$ | $100$ | Guaranteed that $M$ is prime | | $7$ | $500$ | None | | $8$ | $500$ | Guaranteed that $M$ is prime | | $9$ | $500$ | None | | $10$ | $500$ | Guaranteed that $M$ is prime | Translated by ChatGPT 5