102816: [AtCoder]ABC281 G - Farthest City
Description
Score : $600$ points
Problem Statement
You are given positive integers $N$ and $M$.
Find the number, modulo $M$, of simple connected undirected graphs with $N$ vertices numbered $1, \dots, N$ that satisfy the following condition.
- For every $u = 2, \dots, N-1$, the shortest distance from vertex $1$ to vertex $u$ is strictly smaller than the shortest distance from vertex $1$ to vertex $N$.
Here, the shortest distance from vertex $u$ to vertex $v$ is the minimum number of edges in a simple path connecting vertices $u$ and $v$.
Two graphs are considered different if and only if there are two vertices $u$ and $v$ that are connected by an edge in exactly one of those graphs.
Constraints
- $3 \leq N \leq 500$
- $10^8 \leq M \leq 10^9$
- $N$ and $M$ are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$
Output
Print the answer.
Sample Input 1
4 1000000000
Sample Output 1
8
The following eight graphs satisfy the condition.
Sample Input 2
3 100000000
Sample Output 2
1
Sample Input 3
500 987654321
Sample Output 3
610860515
Be sure to find the number modulo $M$.
Input
题意翻译
构造一张 $N$ 个点的无向连通图，边权都是 $1$。记图中 $1$ 到 $u$ 的最短路径长度为 $d_u$，你需要保证 $\max\{d_1,d_2,...,d_{N-1}\}$ **严格小于** $d_N$。求构造方案数模 $M$ 的值，方案区分节点编号。Output
得分：600分
问题描述
给你两个正整数 $N$ 和 $M$。
- 求满足以下条件的简单连通无向图的数量（对 $M$ 取模）。
- 对于每个 $u = 2, \dots, N-1$，从顶点 $1$ 到顶点 $u$ 的最短距离严格小于从顶点 $1$ 到顶点 $N$ 的最短距离。
这里，从顶点 $u$ 到顶点 $v$ 的最短距离是连接顶点 $u$ 和 $v$ 的简单路径中边的数量的最小值。
只有当存在两个顶点 $u$ 和 $v$，它们在其中一个图中由一条边连接而在另一个图中不连接时，两个图才被认为是不同的。
约束
- $3 \leq N \leq 500$
- $10^8 \leq M \leq 10^9$
- $N$ 和 $M$ 是整数。
输入
输入数据通过标准输入以以下格式给出：
$N$ $M$
输出
输出答案。
样例输入 1
4 1000000000
样例输出 1
8
以下八个图满足条件。
样例输入 2
3 100000000
样例输出 2
1
样例输入 3
500 987654321
样例输出 3
610860515
确保找到对 $M$ 取模后的数量。