Keep Connect

题目描述

你得到一个整数 $N$（$N\ge 2$）和一个素数 $P$。
考虑图 $G$，它有 $2N$ 个顶点和 $(3N-2)$ 条边，如下图所示。

更具体地，边按如下方式连接顶点，顶点按 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$，求解下列问题。

计算在 $3N-2$ 条边中恰好删除 $i$ 条边且使得得到的图仍然连通的方式数，对 $P$ 取模。

输入格式

输入按照标准输入给出，格式如下： $N$ $P$

输出格式

打印 $N-1$ 个整数，第 $i$ 个数为 $k=i$ 时的答案，数字之间用空格分隔。

3 998244353

7 15

16 999999937

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$ 是素数。在 $N=3$ 的情况下，有 $7$ 种方法可以删除恰好一条边且使得到的图仍然连通，如下所示。 有 $15$ 种方法可以删除恰好两条边且使得到的图仍然连通，如下所示。 因此，对于 $P=998244353$，应当按此顺序输出这些模 $P$ 的数：$7$ 和 $15$。
注意输出对 $P$ 取模的结果。

标签: AtCoder|abc248F

来源

AtCoder|abc248F