/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
2 以上の整数 N および素数 P が与えられます。
下図のような 2N 頂点 (3N-2) 辺のグラフ G を考えます。
より具体的には、頂点を順に頂点 1, 頂点 2, \ldots, 頂点 2N、 辺を順に辺 1, 辺 2, \ldots, 辺 (3N-2) とすると、各辺は次のように頂点を結んでいます。
- 1\leq i\leq N-1 について、辺 i は頂点 i と頂点 i+1 を結んでいる。
- 1\leq i\leq N-1 について、辺 (N-1+i) は頂点 N+i と頂点 N+i+1 を結んでいる。
- 1\leq i\leq N について、辺 (2N-2+i) は頂点 i と頂点 N+i を結んでいる。
i=1,2,\ldots ,N-1 について、次の問題を解いてください。
G の 3N-2 本の辺からちょうど i 本の辺を取り除く方法であって、辺を取り除いた後のグラフも連結であるようなものの個数を P で割ったあまりを求めよ。
制約
- 2 \leq N \leq 3000
- 9\times 10^8 \leq P \leq 10^9
- N は整数である。
- P は素数である。
入力
入力は以下の形式で標準入力から与えられる。
N P
出力
N-1 個の整数を空白区切りで出力せよ。 ただし、k 番目の整数は i=k に対する答えである。
入力例 1
3 998244353
出力例 1
7 15
N=3 の場合について、取り除いた後のグラフも連結となるように、ちょうど 1 本の辺を取り除く方法は次の 7 通りです。
取り除いた後のグラフも連結となるように、ちょうど 2 本の辺を取り除く方法は次の 15 通りです。
よって、これらを P=998244353 で割ったあまりである 7, 15 をこの順に出力します。
入力例 2
16 999999937
出力例 2
46 1016 14288 143044 1079816 6349672 29622112 110569766 330377828 784245480 453609503 38603306 44981526 314279703 408855776
P で割ったあまりを出力することに注意してください。
Score : 500 points
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.