LibreOJ

552 「LibreOJ Round #8」MIN&MAX I

内存限制：256 MB 时间限制：1000 ms

题目描述

对于一个 $n$ 阶排列 $p$，我们建立一张**无向简单图** $G(p)$，有 $n$ 个节点，标号从 $1$ 到 $n$，每个点向左右两侧最近的比它大的点以及比它小的点连边。 形式化地，在 $G(p)$ 中，$\forall u p_v$，且不存在 $u < i < v$ 满足 $p_u > p_i$； * $p_u < p_v$，且不存在 $u < i < v$ 满足 $p_i < p_v$； * $p_u > p_v$，且不存在 $u < i < v$ 满足 $p_i > p_v$。 现在在所有的 $n$ 阶排列中随机选择一个排列 $p$，请求出 $G(p)$ 中三元简单环的期望个数，答案对 $998244353$ 取模。

输入格式

一行一个正整数 $n$。

输出格式

一行一个整数 $\mathrm{ans}$ 表示答案。

样例 1

在所有 $n!$ 种排列中共有 $4$ 个三元简单环（${1,3,2},{2,3,1},{2,1,3},{3,1,2}$ 各一个），所以答案为 $\frac{4}{3!}=\frac{2}{3}$，即 $2\times 3^{-1} \pmod{998244353}=665496236$。

样例 2

样例 3

样例 4

数据范围与提示

对于所有数据，$1\le n < 998244353$。

详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：

Subtask # 分值（百分比） $n$
$1$ $15$ $\le 10$
$2$ $20$ $\le 100$
$3$ $40$ $\le 10^6$
$4$ $15$ $\ge 998000000$
$5$ $10$ -

样例

样例输入 1

3

样例输出 1

665496236

样例输入 2

91

样例输出 2

116578319

样例输入 3

3

样例输出 3

665496236

样例输入 4

91

样例输出 4

116578319