#P10277. [2023年重庆八中省队模拟]物种共产

    ID: 9395 传统题 6000ms 1024MiB 尝试: 19 已通过: 2 难度: 8 上传者: 标签>组合数学数论贪心CF2400数学模运算构造

[2023年重庆八中省队模拟]物种共产

物种共产(speciescommunism)

题目描述

给定整数 n,m,modn,m,\mathrm{mod},求能够通过下述过程产生的不同整数序列 a=(a1,…,an)a=(a_1,\ldots,a_n) 的数量,答案对输入的质数 mod\mathrm{mod} 取模:

  1. 选择一个 nn 个节点、mm 条边的连通无向图 GG,没有自环,允许重边。节点的度数按边的条数计,重边分别贡献度数。
  2. 从任意根节点开始深度优先遍历。每个节点第一次被访问时,将它的度数追加到序列末尾。每个节点的邻接表顺序可以任意选择。

相同序列无论由多少种图或遍历得到,都只统计一次。过程可写为:

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)

例如 n=4,m=5n=4,m=5 时,可以得到序列 (2,4,1,3)(2,4,1,3):

图中节点数字表示首次访问的顺序,橙色箭头表示 DFS 经过的树边。

输入格式

一行三个整数 n,m,modn,m,\mathrm{mod}。

输出格式

输出一个整数,表示不同序列的数量对 mod\mathrm{mod} 取模的结果。

样例 1 输入

2 2 998244353

样例 1 输出

1

数据范围

全部数据满足 2≤n≤1072\le n\le10^7,n−1≤m≤107n-1\le m\le10^7,107<mod≤109+910^7<\mathrm{mod}\le10^9+9,且 mod\mathrm{mod} 为质数。

子任务 分值 nn 上限 mm 上限 特殊性质 依赖
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:m=n−1m=n-1。
  • B:m=nm=n。
  • C:mod=998244353\mathrm{mod}=998244353。