Score : $650$ points

问题描述

Snuke 提出了以下问题。

给定两个排列 $P=(P_1,P_2,\ldots,P_N)$ 和 $Q=(Q_1,Q_2,\ldots,Q_N)$，它们都是 $(1,2,\ldots,N)$ 的排列。现在我们按照以下方式构建一个包含 $N$ 个顶点和 $N$ 条边的图。

• 对于 $i=1,2,\ldots,N$ 按照顺序，在顶点 $i$ 和 $P_i$ 之间绘制一条权重为 $Q_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$ 种输入中，求出（模 $998244353$）使得 Alice 和 Bob 的解决方案都无法给出正确答案的输入数量。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 09:06:05