103187: [Atcoder]ABC318 Ex - Count Strong Test Cases

Problem Statement

Snuke has come up with the following problem.

You are given permutations $P=(P_1,P_2,\ldots,P_N)$ and $Q=(Q_1,Q_2,\ldots,Q_N)$ of $(1,2,\ldots,N)$. Let us build a graph with $N$ vertices and $N$ edges as follows.

• For $i=1,2,\ldots,N$ in this order, draw an edge of weight $Q_i$ connecting vertices $i$ and $P_i$ bidirectionally.

When removing some number of edges to eliminate cycles from the graph, find the minimum possible total weight of the removed edges.

Alice and Bob came up with the following solutions.

Alice: Initialize the answer to $0$. For $i=1,2,\ldots,N$ in this order, if the edge connecting vertices $i$ and $P_i$ is contained in a cycle, remove that edge and add its weight to the answer.

Bob: Initialize the answer to $0$. For $i=N,N-1,\ldots,1$ in this order, if the edge connecting vertices $i$ and $P_i$ is contained in a cycle, remove that edge and add its weight to the answer.

Snuke has realized that their solutions are both incorrect, and he wants to know the number of inputs for which neither of their solutions gives the correct answer.

Among the $(N!)^2$ possible inputs, find the number, modulo $998244353$, of inputs for which neither Alice's nor Bob's solution gives the correct answer.

Constraints

• $1\leq N\leq 2\times 10^5$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ 

Output

Print the answer as an integer.

Sample Input 1

3

Sample Output 1

4

The following four inputs satisfy the condition.

• $P=(2,3,1),Q=(2,1,3)$
• $P=(2,3,1),Q=(3,1,2)$
• $P=(3,1,2),Q=(2,1,3)$
• $P=(3,1,2),Q=(3,1,2)$

For example, for the input $P=(2,3,1),Q=(2,1,3)$, the correct answer is $1$, but Alice's solution gives $2$ and Bob's gives $3$.

Sample Input 2

2

Sample Output 2

0

There may be no inputs that satisfy the condition.

Sample Input 3

6

Sample Output 3

314708

Sample Input 4

318

Sample Output 4

321484323

问题描述

Snuke提出了以下问题。

给你两个$(1,2,\ldots,N)$的排列$P=(P_1,P_2,\ldots,P_N)$和$Q=(Q_1,Q_2,\ldots,Q_N)$。 按照以下方式构建一个有$N$个顶点和$N$条边的图。

• 按照顺序，从$i=1,2,\ldots,N$，画一条权值为$Q_i$的双向边连接顶点$i$和$P_i$。

当删除一些边以消除图中的循环时，找到删除的边的最小可能总权值。

Alice和Bob提出了以下解决方案。

Alice: 将答案初始化为0。按照顺序，从$i=1,2,\ldots,N$，如果连接顶点$i$和$P_i$的边包含在一个循环中，删除这条边，并将其权值添加到答案中。

Bob: 将答案初始化为0。按照顺序，从$i=N,N-1,\ldots,1$，如果连接顶点$i$和$P_i$的边包含在一个循环中，删除这条边，并将其权值添加到答案中。

Snuke已经意识到他们的解决方案都是错误的，他想知道有多少输入是他们的解决方案都无法给出正确答案的。

在可能的$(N!)^2$个输入中，找出在Alice和Bob的解决方案都无法给出正确答案的输入数量，对$998244353$取模。

约束

• $1\leq N\leq 2\times 10^5$
• 所有输入值都是整数。

输入

输入从标准输入给出，格式如下：

$N$ 

输出

打印答案作为整数。

样例输入 1

3

样例输出 1

4

有以下四个输入满足条件。

• $P=(2,3,1),Q=(2,1,3)$
• $P=(2,3,1),Q=(3,1,2)$
• $P=(3,1,2),Q=(2,1,3)$
• $P=(3,1,2),Q=(3,1,2)$

例如，对于输入$P=(2,3,1),Q=(2,1,3)$，正确的答案是$1$，但Alice的解决方案给出$2$，Bob的给出$3$。

样例输入 2

2

样例输出 2

0

可能没有满足条件的输入。

样例输入 3

6

样例输出 3

314708

样例输入 4

318

样例输出 4

321484323