Score : $600$ points

问题描述

给定正整数 $N$ 和 $M$。

求满足以下条件的简单连通无向图的数量，对模 $M$。

• 对于所有 $u = 2, \dots, N-1$，从顶点 $1$ 到顶点 $u$ 的最短距离严格小于从顶点 $1$ 到顶点 $N$ 的最短距离。

这里，从顶点 $u$ 到顶点 $v$ 的最短距离是在一条简单路径中连接顶点 $u$ 和 $v$ 的最少边数。
两个图仅当存在两个顶点 $u$ 和 $v$ 在其中一个图中通过一条边相连而在另一个图中没有相连时，被认为是不同的。

以上为通义千问 qwen-max 翻译，仅供参考。

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$.

update @ 2024/3/10 11:49:01