Score : $500$ points

问题描述

给定一个大于等于2的整数 $N$ 和一个质数 $P$。
考虑下图所示具有2N个顶点和（3N-2）条边的图 $G$。

更具体地说，边连接顶点的方式如下，其中顶点标记为Vertex $1$, Vertex $2$, $\ldots$, Vertex $2N$，边标记为Edge $1$, Edge $2$, $\ldots$, Edge $(3N-2)$。

• 对于每个 $1\leq i\leq N-1$，Edge $i$ 连接Vertex $i$ 和 Vertex $i+1$。
• 对于每个 $1\leq i\leq N-1$，Edge $(N-1+i)$ 连接Vertex $N+i$ 和 Vertex $N+i+1$。
• 对于每个 $1\leq i\leq N$，Edge $(2N-2+i)$ 连接Vertex $i$ 和 Vertex $N+i$。

对于 $i=1,2,\ldots ,N-1$，解决以下问题。

求在模 $P$ 下，从 $G$ 的 $3N-2$ 条边中恰好移除 $i$ 条边，使得得到的图仍然保持连通的方法数量。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given an integer $N$ greater than or equal to $2$ and a prime $P$.
Consider the graph $G$ with $2N$ vertices and $(3N-2)$ edges shown in the figure below.

More specifically, the edges connect the vertices as follows, where the vertices are labeled as Vertex $1$, Vertex $2$, $\ldots$, Vertex $2N$, and the edges are labeled as Edge $1$, Edge $2$, $\ldots$, Edge $(3N-2)$.

• For each $1\leq i\leq N-1$, Edge $i$ connects Vertex $i$ and Vertex $i+1$.
• For each $1\leq i\leq N-1$, Edge $(N-1+i)$ connects Vertex $N+i$ and Vertex $N+i+1$.
• For each $1\leq i\leq N$, Edge $(2N-2+i)$ connects Vertex $i$ and Vertex $N+i$.

For each $i=1,2,\ldots ,N-1$, solve the following problem.

Find the number of ways, modulo $P$, to remove exactly $i$ of the $3N-2$ edges of $G$ so that the resulting graph is still connected.

Constraints

• $2 \leq N \leq 3000$
• $9\times 10^8 \leq P \leq 10^9$
• $N$ is an integer.
• $P$ is a prime.

Input

Input is given from Standard Input in the following format:

$N$ $P$

Output

Print $N-1$ integers, the $i$-th of which is the answer for $i=k$, separated by spaces.

Sample Input 1

3 998244353

Sample Output 1

7 15

In the case $N=3$, there are $7$ ways, shown below, to remove exactly one edge so that the resulting graph is still connected.

There are $15$ ways, shown below, to remove exactly two edges so that the resulting graph is still connected.

Thus, these numbers modulo $P=998244353$ should be printed: $7$ and $15$, in this order.

Sample Input 2

16 999999937

Sample Output 2

46 1016 14288 143044 1079816 6349672 29622112 110569766 330377828 784245480 453609503 38603306 44981526 314279703 408855776

Be sure to print the numbers modulo $P$.

update @ 2024/3/10 10:37:43