/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 650 点
問題文
すぬけくんは以下の問題を考えました。
(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 の解法がどちらも誤っていることに気付いたので、二人の解法の答えが共に正しい答えと異なるような入力の個数が知りたくなりました。
入力は (N!)^2 通り考えられますが、その内 Alice と Bob の解法の答えが共に正しい答えと異なるものの個数を 998244353 で割ったあまりを求めてください。
制約
- 1\leq N\leq 2\times 10^5
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
3
出力例 1
4
条件を満たす入力は以下の 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
Score : 650 points
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