UOJ Logo Universal Online Judge

UOJ

#961. 【UR #30】赛场设计

附件下载 统计

English Problem Statement

伏特正在设计马拉松赛场的道路,以确保物资运输和观众流动的秩序。

伏特选定了 $n$ 个站点,他可以在 $n$ 个站点之间铺设若干单向道路,不能铺设重复的道路。

伏特不希望跳蚤们迷路:铺设的道路不能有环。

伏特希望赛场道路有良好的交通:不能存在三个站点 $(a,b,c)$,使得 $a$ 不能到达 $b$,$b$ 不能到达 $c$,$c$ 不能到达 $a$。

称满足上述两条限制的道路铺设方案为好图。伏特想知道好图有多少种,这个数字可能很大,你需要求出答案在模素数 $P$ 意义下的值。

输入格式

一行两个整数,分别表示 $n$ 和 $P$。

输出格式

一行一个整数,表示答案对 $P$ 取模的值。

样例一

input

3 835199921

output

18

explanation

下记 $(x,y)$ 表示 $x$ 到 $y$ 的单向道路。

选择边集 $(1,2),(1,3)$ 是好图,通过交换点的标号可以获得 3 种好图。

选择边集 $(1,2),(2,3)$ 是好图,通过交换点的标号可以获得 6 种好图。

选择边集 $(1,2),(1,3),(2,3)$ 是好图,通过交换点的标号可以获得 6 种好图。

选择边集 $(1,3),(2,3)$ 是好图,通过交换点的标号可以获得 3 种好图。

选择边集 $(1,2)$ 不是好图,因为存在:$1$ 无法到 $3$,$3$ 无法到 $2$,$2$ 无法到 $1$。

选择边集 $(1,2),(2,1)$ 不是好图,因为存在环 $(1,2),(2,1)$,不属于 DAG。

一共有 $3+6+6+3=18$ 种三个点的好图。

样例二

input

16 828234769

output

372590002

样例三~九

见附件下载。

对于所有样例,保证第 $i$ 个样例满足第 $i$ 个子任务的约束。

数据范围

对于所有数据,保证 $1\le n\le 10^6$,$10^8\le P\le 10^9$,$P$ 是素数。

子任务编号 分值 $n\le$ 特殊性质
$1$ $12$ $5$
$2$ $12$ $18$
$3$ $8$ $200$
$4$ $10$ $5000$ $P=998244353$
$5$ $10$ $5000$
$6$ $12$ $2\times 10^5$ $P=998244353$
$7$ $12$ $2\times 10^5$
$8$ $12$ $10^6$ $P=998244353$
$9$ $12$ $10^6$

时间限制:$\texttt{1s}$

空间限制:$\texttt{512MB}$