102485: [AtCoder]ABC248 F - Keep Connect
Description
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$.
Input
题意翻译
给定 $ n, p $，存在如图的 $ 2 \times n $ 的网格图，显然初始共有 $ 2n $ 个顶点和 $ 3n - 2 $ 条边，分别求删除 $ i \in [1, n - 1] $ 条边后仍使图连通的删边方案数，对 $ p $ 取模。Output
更具体地说，边连接顶点如下，其中顶点标记为顶点1，顶点2，…，顶点2N，边标记为边1，边2，…，边（3N-2）。
- 对于每个$1≤i≤N-1$，边i连接顶点i和顶点i+1。
- 对于每个$1≤i≤N-1$，边（N-1+i）连接顶点N+i和顶点N+i+1。
- 对于每个$1≤i≤N$，边（2N-2+i）连接顶点i和顶点N+i。
部分 约束条件找出从G的3N-2条边中恰好移除i条边的方法数，使得结果图仍然是连通的。
- $2≤N≤3000$
- $9×10^8≤P≤10^9$
- N是整数。
- P是素数。
在N=3的情况下，如下图所示，有7种方法可以恰好移除一条边，使得结果图仍然是连通的。
如下图所示，有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取模的数。