#552. 「LibreOJ Round #8」MIN&MAX I

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: liu_cheng_ao

题目描述

对于一个 nn 阶排列 pp,我们建立一张无向简单图 G(p)G(p),有 nn 个节点,标号从 11nn,每个点向左右两侧最近的比它大的点以及比它小的点连边。
形式化地,在 G(p)G(p) 中,u<v\forall u<v,边 (u,v)(u,v) 存在当且仅当以下四个条件至少一个成立:

  • pu<pvp_u<p_v,且不存在 u<i<vu<i<v 满足 pu<pip_u<p_i
  • pu>pvp_u>p_v,且不存在 u<i<vu<i<v 满足 pu>pip_u>p_i
  • pu<pvp_u<p_v,且不存在 u<i<vu<i<v 满足 pi<pvp_i<p_v
  • pu>pvp_u>p_v,且不存在 u<i<vu<i<v 满足 pi>pvp_i>p_v

现在在所有的 nn 阶排列中随机选择一个排列 pp,请求出 G(p)G(p) 中三元简单环的期望个数,答案对 998244353998244353 取模。

For an nn-order permutation pp, we set up an undirected simple graph G(p)G(p) with nn vertices numbered from 11 to nn. We create an edge between each vertice ii and the nearest vertices in each side which correspond a greater (or less) pp value than pip_i.
Formally,in this graph, u<v\forall u<v, the edge (u,v)(u, v) exists iff at least one of the following four conditions hold:

  • pu<pvp_u<p_v, and no u<i<vu<i<v exists such that pu<pip_u<p_i;
  • pu>pvp_u>p_v, and no u<i<vu<i<v exists such that pu>pip_u>p_i;
  • pu<pvp_u<p_v, and no u<i<vu<i<v exists such that pi<pvp_i<p_v;
  • pu>pvp_u>p_v, and no u<i<vu<i<v exists such that pi>pvp_i>p_v.

Now we randomly choose a permutation pp from all nn-order permutations. Your task is to calculate the expected number of the 33-cycles in G(p)G(p). You only need to output the answer modulo 998244353998244353.

输入格式

一行一个正整数 nn

The only line contains a positive integer nn which means the order of the permutation.

输出格式

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

Output only one line,which contains an integer ans\mathrm{ans} which means the expected number of the 33-cycles in G(p)G(p) modulo 998244353998244353.

样例

样例输入 1

3

样例输出 1

665496236

样例解释 1

在所有 n!n! 种排列中共有 44 个三元简单环({1,3,2},{2,3,1},{2,1,3},{3,1,2}\{1,3,2\},\{2,3,1\},\{2,1,3\},\{3,1,2\} 各一个),所以答案为 43!=23\frac{4}{3!}=\frac{2}{3},即 2×31(mod998244353)=6654962362\times 3^{-1} \pmod{998244353}=665496236

样例输入 2

91

样例输出 2

116578319

Sample Input 1

3

Sample Output 1

665496236

Sample Explanation 1

It is easy to count that there are four 33-cycles in total from the 3!3! permutations(each of {1,3,2},{2,3,1},{2,1,3},{3,1,2}\{1,3,2\},\{2,3,1\},\{2,1,3\},\{3,1,2\} has one). So answer is 43!=23\frac{4}{3!}=\frac{2}{3},that is, 2×31(mod998244353)=6654962362\times 3^{-1} \pmod{998244353}=665496236.

Sample Input 2

91

Sample Output 2

116578319

数据范围与提示

对于所有数据,1n<9982443531\le n<998244353

详细的数据限制及约定如下(留空表示和上述所有数据的约定相同):

Subtask # 分值(百分比) nn
11 1515 10\le 10
22 2020 100\le 100
33 4040 106\le 10^6
44 1515 998000000\ge 998000000
55 1010 -

For all test cases, 1n<9982443531\le n<998244353.

Detailed constraints and hints are as follows (blank grids denote the same constraints as mentioned above):

Subtask # Score (percentage) nn
11 1515 10\le 10
22 2020 100\le 100
33 4040 106\le 10^6
44 1515 998000000\ge 998000000
55 1010 -