[ABC248F] Keep Connect

题面翻译

给定 $n, p$ ，存在如图的 $2 \times n$ 的网格图，显然初始共有 $2n$ 个顶点和 $3n - 2$ 条边，分别求删除 $i \in [1, n - 1]$ 条边后仍使图连通的删边方案数，对 $p$ 取模。

题目描述

$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$ で割ったあまりを求めよ。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $P$

输出格式

$N-1$ 個の整数を空白区切りで出力せよ。ただし、 $k$ 番目の整数は $i=k$ に対する答えである。

样例 #1

样例输入 #1

3 998244353

样例输出 #1

7 15

样例 #2

样例输入 #2

16 999999937

样例输出 #2

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

提示

制約

$2\ \leq\ N\ \leq\ 3000$
$9\times\ 10^8\ \leq\ P\ \leq\ 10^9$
$N$ は整数である。
$P$ は素数である。

Sample Explanation 1

$N=3$ の場合について、取り除いた後のグラフも連結となるように、ちょうど $1$ 本の辺を取り除く方法は次の $7$ 通りです。取り除いた後のグラフも連結となるように、ちょうど $2$ 本の辺を取り除く方法は次の $15$ 通りです。よって、これらを $P=998244353$ で割ったあまりである $7$ , $15$ をこの順に出力します。

Sample Explanation 2

$P$ で割ったあまりを出力することに注意してください。

# [ABC248F] Keep Connect

## 题面翻译

给定 $ n, p $，存在如图的 $ 2 \times n $ 的网格图，显然初始共有 $ 2n $ 个顶点和 $ 3n - 2 $ 条边，分别求删除 $ i \in [1, n - 1] $ 条边后仍使图连通的删边方案数，对 $ p $ 取模。

## 题目描述

[problemUrl]: https://atcoder.jp/contests/abc248/tasks/abc248_f

$ 2 $ 以上の整数 $ N $ および素数 $ P $ が与えられます。  
 下図のような $ 2N $ 頂点 $ (3N-2) $ 辺のグラフ $ G $ を考えます。

  ![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT_abc248_f/6f63f253a9279fafd6370d1065746906081f4753.png)

より具体的には、頂点を順に頂点 $ 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 $ で割ったあまりを求めよ。

## 输入格式

入力は以下の形式で標準入力から与えられる。

> $ N $ $ P $

## 输出格式

$ N-1 $ 個の整数を空白区切りで出力せよ。 ただし、$ k $ 番目の整数は $ i=k $ に対する答えである。

## 样例 #1

### 样例输入 #1

```
3 998244353
```

### 样例输出 #1

```
7 15
```

## 样例 #2

### 样例输入 #2

```
16 999999937
```

### 样例输出 #2

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

## 提示

### 制約

- $ 2\ \leq\ N\ \leq\ 3000 $
- $ 9\times\ 10^8\ \leq\ P\ \leq\ 10^9 $
- $ N $ は整数である。
- $ P $ は素数である。

### Sample Explanation 1

$ N=3 $ の場合について、取り除いた後のグラフも連結となるように、ちょうど $ 1 $ 本の辺を取り除く方法は次の $ 7 $ 通りです。 ![](https://img.atcoder.jp/abc248/57f65600b77ee654900cff4ea6e40872.png) 取り除いた後のグラフも連結となるように、ちょうど $ 2 $ 本の辺を取り除く方法は次の $ 15 $ 通りです。 ![](https://img.atcoder.jp/abc248/3a7d6523a1252886e9a33204a32e45f5.png) よって、これらを $ P=998244353 $ で割ったあまりである $ 7 $, $ 15 $ をこの順に出力します。

### Sample Explanation 2

$ P $ で割ったあまりを出力することに注意してください。

2024/9/4 09:19