P3862 数圈

题目描述

求 $n$ 个点的无向完全图删去一条边之后圈的个数，答案模 $998244353$。

注：圈指的是任选一个顶点为起点，沿着不重复的边，经过不重复的顶点为途径，之后又回到起点的闭合途径。

输入格式

第一行一个整数 $T$，表示数据组数。

接下来 $T$ 行，每行一个整数 $n$，意义如描述所述。

输出格式

一共 $T$ 行，每行一个整数，表示答案。

输入输出样例 #1

输入 #1

4
3
4
5
6

输出 #1

0
3
22
133

说明/提示

前 $10\mathrm{\%}$ 的数据满足 $3\le n\le 10$

另外 $20\mathrm{\%}$ 的数据满足 $ 9.99\times 10^2 \leq n \leq 10^3$

另外 $30\mathrm{\%}$ 的数据满足 $ 9.99\times 10^4 \leq n \leq 10^5$

另外 $40\mathrm{\%}$ 的数据满足 $ 9.99\times 10^8 \leq n \leq 10^9$

所有数据满足 $1\le T\le 10$

题解

用 $f(n)$ 表示本题的答案，$g(n)$ 表示 $n$ 个点的完全图中的环数，$h(n)$ 表示 $n$ 个点的完全图中某特定两点间的路径数。

考虑在 $n-1$ 个点的完全图中增加一个点 $n$，成为 $n$ 个点的完全图删去一条边之后的图，不妨设 $n$ 和 $n-1$ 之间没有边。显然，$g(n-1)$ 中的环必然在 $f(n)$ 中。另外与点 $n$ 有关的环，必然是 $a\to n\to b\to \cdots \to a$ 的形式，其中 $1\le a,b\le n-2$。因此有：

$$f(n)=g(n-1)+C_{n-2}^{2}h(n-1)$$

考虑在 $n-1$ 个点的完全图中增加一个点 $n$，成为 $n$ 个点的完全图。显然，$g(n-1)$ 中的环必然在 $g(n)$ 中。另外与点 $n$ 有关的环，必然是 $a\to n\to b\to \cdots \to a$ 的形式，其中 $1\le a,b\le n-1$。因此有：

$$g(n)=g(n-1)+C_{n-1}^{2}h(n-1)$$

对于 $h(n)$，显然有

$$h(n)=\sum _{i=0}^{n-2}{A}_{n-2}^i$$

转化为递推式

$$h(n)=(n-2)\times h(n-1)+1$$

线性递推可以解决 60% 的数据。对于最后 40% 的数据，$n$ 的取值区间只有 ${10}^6$，打表后递推即可。