AT_abc318_h [ABC318Ex] Count Strong Test Cases

题目描述

すぬけ君想出了如下的问题。

给定 $(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$，依次将顶点 $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$ 之间的边在环中，则删除这条边，并将其权值加到答案中。

すぬけ君发现 Alice 和 Bob 的解法都是错误的，所以他想知道，有多少组输入使得 Alice 和 Bob 的解法的答案都与正确答案不同。

输入共有 $(N!)^2$ 种可能，请你输出其中 Alice 和 Bob 的解法的答案都与正确答案不同的输入的个数，模 $998244353$。

输入格式

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

$N$

输出格式

请输出一个整数，表示答案。

输入输出样例 #1

输入 #1

3

输出 #1

4

输入输出样例 #2

输入 #2

2

输出 #2

0

输入输出样例 #3

输入 #3

6

输出 #3

314708

输入输出样例 #4

输入 #4

318

输出 #4

321484323

说明/提示

限制条件

• $1\leq N\leq 2\times 10^5$
• 输入的所有数均为整数

样例解释 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

也有可能不存在满足条件的输入。

由 ChatGPT 4.1 翻译