#P13122. [AGC067E] Biconnected Graph

    ID: 12306 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3000动态规划组合数学图论计数DP生成函数

[AGC067E] Biconnected Graph

题目描述

给定整数 NN 和素数 PP。

请计算满足以下条件的、编号为 11 到 NN 的 NN 个顶点的连通无向图的个数,并输出其对 PP 取模的结果。

  • 图 GG 中没有自环。允许存在重边。
  • 对于 GG 的每一条边 (u,v)(u,v),即使将 (u,v)(u,v) 从 GG 中删除,GG 依然保持连通。也就是说,GG 是边双连通的。
  • 对于 GG 的每一条边 (u,v)(u,v),如果将 (u,v)(u,v) 从 GG 中删除,GG 就不再是边双连通的。

当且仅当存在一对不同的顶点 (u,v)(u,v),使得两张图中连接 uu 和 vv 的边的数量不同,则认为这两张图不同。

输入格式

输入从标准输入中读取,格式如下:

NN PP

输出格式

输出答案。

输入输出样例 #1

输入 #1

2 1005976817

输出 #1

1

输入输出样例 #2

输入 #2

5 1000837403

输出 #2

372

输入输出样例 #3

输入 #3

10 1001160547

输出 #3

789846604

输入输出样例 #4

输入 #4

20 1006779551

输出 #4

888612770

说明/提示

限制

  • 2≤N≤502 \leq N \leq 50
  • 109<P<1.01×10910^9 < P < 1.01 \times 10^9
  • PP 是素数。
  • 所有输入值均为整数。