#P10277. [2023年重庆八中省队模拟]物种共产
[2023年重庆八中省队模拟]物种共产
物种共产(speciescommunism)
题目描述
给定整数 ,求能够通过下述过程产生的不同整数序列 的数量,答案对输入的质数 取模:
- 选择一个 个节点、 条边的连通无向图 ,没有自环,允许重边。节点的度数按边的条数计,重边分别贡献度数。
- 从任意根节点开始深度优先遍历。每个节点第一次被访问时,将它的度数追加到序列末尾。每个节点的邻接表顺序可以任意选择。
相同序列无论由多少种图或遍历得到,都只统计一次。过程可写为:
a = []
visited = [False] * n
def dfs(x):
visited[x] = True
a.append(degree[x])
for y in g[x]:
if not visited[y]:
dfs(y)
dfs(arbitrary_root)
例如 时,可以得到序列 :

图中节点数字表示首次访问的顺序,橙色箭头表示 DFS 经过的树边。
输入格式
一行三个整数 。
输出格式
输出一个整数,表示不同序列的数量对 取模的结果。
样例 1 输入
2 2 998244353
样例 1 输出
1
数据范围
全部数据满足 ,,,且 为质数。
| 子任务 | 分值 | 上限 | 上限 | 特殊性质 | 依赖 |
|---|---|---|---|---|---|
| 1 | 10 | 6 | 15 | 无 | 无 |
| 2 | 10 | 45 | 1 | ||
| 3 | 整体范围 | A | 无 | ||
| 4 | 15 | B | |||
| 5 | 500 | 无 | 2 | ||
| 6 | 20 | 200000 | 5 | ||
| 7 | 2 | 1000000 | C | 无 | |
| 8 | 18 | 整体范围 | 无 | 3、4、6、7 | |
- A:。
- B:。
- C:。