题目描述
求 $n$ 个点的无向完全图删去一条边之后圈的个数，答案模 $998244353$。
注：圈指的是任选一个顶点为起点，沿着不重复的边，经过不重复的顶点为途径，之后又回到起点的闭合途径。
输入格式
第一行一个整数 $T$，表示数据组数。
接下来 $T$ 行，每行一个整数 $n$，意义如描述所述。
输出格式
一共 $T$ 行，每行一个整数，表示答案。
输入输出样例 #1
输入 #1
1 | |
输出 #1
1 | |
说明/提示
前 $10%$ 的数据满足 $3 \leq n \leq 10$
另外 $20%$ 的数据满足 $ 9.99\times 10^2 \leq n \leq 10^3$
另外 $30%$ 的数据满足 $ 9.99\times 10^4 \leq n \leq 10^5$
另外 $40%$ 的数据满足 $ 9.99\times 10^8 \leq n \leq 10^9$
所有数据满足 $1 \leq T \leq 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 \dots \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 \dots \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$，打表后递推即可。
