実行時間制限: 5 sec / メモリ制限: 1024 MiB
配点 : 800 点
問題文
(1,2,\dots,N) の順列 P=(P_1,P_2,\dots,P_N),Q=(Q_1,Q_2,\dots,Q_N) が与えられます。
P,Q に対して、以下の操作のいずれか一つを選び行うことを M 回繰り返します。
- 1 \le i < j \le N を満たす整数 i,j を選び、P_i,P_j を入れ替える。
- 1 \le i < j \le N を満たす整数 i,j を選び、Q_i,Q_j を入れ替える。
- 1 \le i \le N を満たす整数 i を選び、P_i,Q_i を入れ替える。
M 回の操作終了後に P,Q がいずれも (1,2,\dots,N) の順列になるような操作列の個数を 998244353 で割った余りを求めてください。
制約
- 1 \le N,M \le 500
- P,Q は (1,2,\dots,N) の順列
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M P_1\ P_2\ \dots\ P_N Q_1\ Q_2\ \dots\ Q_N
出力
答えを出力せよ。
入力例 1
3 1 1 2 3 1 3 2
出力例 1
7
例えば、以下のような操作列は条件を満たします。
- 3 種類目の操作で i = 1 を選び、P_1,Q_1 を入れ替える。P=(1,2,3),Q=(1,3,2) となる。
P の要素同士を入れ替える 3 通りの操作と、Q の要素同士を入れ替える 3 通りの操作と、上記の P_1,Q_1 を入れ替える操作の合計 7 通りの操作いずれかひとつからなる操作列が条件を満たします。
入力例 2
3 2 1 2 3 1 3 2
出力例 2
53
入力例 3
8 15 6 4 8 3 2 7 1 5 1 6 4 5 7 2 8 3
出力例 3
571380540
Score : 800 points
Problem Statement
You are given permutations P=(P_1,P_2,\dots,P_N) and Q=(Q_1,Q_2,\dots,Q_N) of (1,2,\dots,N).
For P and Q, you repeat the following M times: choose and perform one of the operations below.
- Choose integers i and j satisfying 1 \le i < j \le N, and swap P_i and P_j.
- Choose integers i and j satisfying 1 \le i < j \le N, and swap Q_i and Q_j.
- Choose an integer i satisfying 1 \le i \le N, and swap P_i and Q_i.
Find the number, modulo 998244353, of sequences of operations such that both P and Q are permutations of (1,2,\dots,N) after the M operations.
Constraints
- 1 \le N,M \le 500
- P and Q are permutations of (1,2,\dots,N).
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M P_1\ P_2\ \dots\ P_N Q_1\ Q_2\ \dots\ Q_N
Output
Output the answer.
Sample Input 1
3 1 1 2 3 1 3 2
Sample Output 1
7
For example, the following sequence of operations satisfies the condition.
- Choose i = 1 in an operation of the third kind to swap P_1 and Q_1. Now P=(1,2,3) and Q=(1,3,2).
Any sequence of operations composed of exactly one of the following seven operations satisfies the condition: the three operations that swap two elements of P, the three operations that swap two elements of Q, and the operation described above that swaps P_1 and Q_1.
Sample Input 2
3 2 1 2 3 1 3 2
Sample Output 2
53
Sample Input 3
8 15 6 4 8 3 2 7 1 5 1 6 4 5 7 2 8 3
Sample Output 3
571380540
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 800 点
問題文
(1,2,\dots,N) の順列 P=(P_1,P_2,\dots,P_N) と長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
頂点に 1 から N の番号が付いた N 頂点の根付き木 T に対して、以下で f(T) を定義します。
(1,2,\dots,N) の順列 Q=(Q_1,Q_2,\dots,Q_N) のうち、以下の条件を満たすものを良い順列と呼ぶ。
- 根以外の全ての頂点 v に対して、v の親を頂点 u とした時、Q において u は v より前に現れる。
良い順列のうち、辞書順最小のものを f(T) とする。
また、N 頂点の根付き木 T のコストを \sum_{i=1}^{N} A_i c_i^2 と定義します。ここで、c_i は T における頂点 i の子の個数です。
N 頂点の根付き木 T のうち f(T) = P を満たすものに対する T のコストの最小値を求めてください。
制約
- 1 \le N \le 2 \times 10^5
- P は (1,2,\dots,N) の順列
- 1 \le A_i \le 10^6
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N P_1\ P_2\ \dots\ P_N A_1\ A_2\ \dots\ A_N
出力
答えを出力せよ。
入力例 1
3 1 2 3 1 2 1
出力例 1
3
T として条件を満たすのは、頂点 1 を根とした木のうち以下の T_1,T_2 の 2 個です。
T_1 のコストは 1 \times 2^2 + 2 \times 0^2 + 1 \times 0^2 = 4、T_2 のコストは 1 \times 1^2 + 2 \times 1^2 + 1 \times 0^2 = 3 であるため、コストの最小値は 3 です。
入力例 2
5 3 1 5 2 4 4 1 1 2 1
出力例 2
6
入力例 3
10 8 4 7 9 1 3 2 10 6 5 816977 838423 186050 232610 582528 327642 432740 420943 194307 966417
出力例 3
3901780
Score : 800 points
Problem Statement
You are given a permutation P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N) and a length-N sequence of positive integers A=(A_1,A_2,\dots,A_N).
For a rooted tree T with N vertices numbered 1 through N, define f(T) as follows.
Among the permutations Q=(Q_1,Q_2,\dots,Q_N) of (1,2,\dots,N), call one that satisfies the following condition a good permutation.
- For every vertex v other than the root, letting u be its parent, u appears before v in Q.
Let f(T) be the lexicographically smallest good permutation.
Also, define the cost of a rooted tree T with N vertices as \sum_{i=1}^{N} A_i c_i^2, where c_i is the number of children of vertex i in T.
Find the minimum cost of a rooted tree T with N vertices satisfying f(T) = P.
Constraints
- 1 \le N \le 2 \times 10^5
- P is a permutation of (1,2,\dots,N).
- 1 \le A_i \le 10^6
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N P_1\ P_2\ \dots\ P_N A_1\ A_2\ \dots\ A_N
Output
Output the answer.
Sample Input 1
3 1 2 3 1 2 1
Sample Output 1
3
The trees satisfying the condition for T are the following two trees, T_1 and T_2, both rooted at vertex 1.
The cost of T_1 is 1 \times 2^2 + 2 \times 0^2 + 1 \times 0^2 = 4, and the cost of T_2 is 1 \times 1^2 + 2 \times 1^2 + 1 \times 0^2 = 3, so the minimum cost is 3.
Sample Input 2
5 3 1 5 2 4 4 1 1 2 1
Sample Output 2
6
Sample Input 3
10 8 4 7 9 1 3 2 10 6 5 816977 838423 186050 232610 582528 327642 432740 420943 194307 966417
Sample Output 3
3901780
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 900 点
問題文
(1,2,\dots,N) の順列 P=(P_1,P_2,\dots,P_N) が与えられます。
(1,2,\dots,N) の部分列 x=(x_1,x_2,\dots,x_k) に対して、以下の手続きによって得られる数列を f(x) と置きます。
- 数列 Q=(Q_1,Q_2,\dots,Q_N) を Q = P で初期化する。
- (Q_{x_1},Q_{x_2},\dots,Q_{x_k}) を昇順に並び替えて得られる数列を A=(A_1,A_2,\dots,A_k) と置く。
- 1 \le i \le k を満たす整数 i に対して、Q_{x_i} を A_i で置き換える。この時点での Q を f(x) とする。
x として考えられるものは空列も含めて 2^N 通りありますが、その全てに対する f(x) の転倒数の総和を 998244353 で割った余りを求めてください。
制約
- 2 \le N \le 2 \times 10^5
- P は (1,2,\dots,N) の順列
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N P_1\ P_2\ \dots\ P_N
出力
答えを出力せよ。
入力例 1
3 3 1 2
出力例 1
12
x としてあり得る 8 通り全てに対する f(x) とその転倒数は以下のようになります。
- x = () のとき、f(x) = (3,1,2) となり転倒数は 2
- x = (1) のとき、f(x) = (3,1,2) となり転倒数は 2
- x = (2) のとき、f(x) = (3,1,2) となり転倒数は 2
- x = (3) のとき、f(x) = (3,1,2) となり転倒数は 2
- x = (1,2) のとき、f(x) = (1,3,2) となり転倒数は 1
- x = (1,3) のとき、f(x) = (2,1,3) となり転倒数は 1
- x = (2,3) のとき、f(x) = (3,1,2) となり転倒数は 2
- x = (1,2,3) のとき、f(x) = (1,2,3) となり転倒数は 0
よって答えは 2+2+2+2+1+1+2+0=12 です。
入力例 2
5 4 2 5 3 1
出力例 2
148
入力例 3
13 2 7 4 9 3 13 8 12 6 5 10 11 1
出力例 3
174080
Score : 900 points
Problem Statement
You are given a permutation P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N).
For a subsequence x=(x_1,x_2,\dots,x_k) of (1,2,\dots,N), let f(x) denote the sequence obtained by the following procedure.
- Initialize the sequence Q=(Q_1,Q_2,\dots,Q_N) with Q = P.
- Let A=(A_1,A_2,\dots,A_k) be the sequence obtained by sorting (Q_{x_1},Q_{x_2},\dots,Q_{x_k}) in ascending order.
- For every integer i satisfying 1 \le i \le k, replace Q_{x_i} with A_i. Let f(x) be Q at this point.
There are 2^N possible choices of x, including the empty sequence. Find the sum, modulo 998244353, of the number of inversions of f(x) over all those choices.
Constraints
- 2 \le N \le 2 \times 10^5
- P is a permutation of (1,2,\dots,N).
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N P_1\ P_2\ \dots\ P_N
Output
Output the answer.
Sample Input 1
3 3 1 2
Sample Output 1
12
f(x) and its number of inversions for all eight possible choices of x are as follows.
- For x = (), we have f(x) = (3,1,2), and the number of inversions is 2.
- For x = (1), we have f(x) = (3,1,2), and the number of inversions is 2.
- For x = (2), we have f(x) = (3,1,2), and the number of inversions is 2.
- For x = (3), we have f(x) = (3,1,2), and the number of inversions is 2.
- For x = (1,2), we have f(x) = (1,3,2), and the number of inversions is 1.
- For x = (1,3), we have f(x) = (2,1,3), and the number of inversions is 1.
- For x = (2,3), we have f(x) = (3,1,2), and the number of inversions is 2.
- For x = (1,2,3), we have f(x) = (1,2,3), and the number of inversions is 0.
Thus, the answer is 2+2+2+2+1+1+2+0=12.
Sample Input 2
5 4 2 5 3 1
Sample Output 2
148
Sample Input 3
13 2 7 4 9 3 13 8 12 6 5 10 11 1
Sample Output 3
174080
実行時間制限: 4 sec / メモリ制限: 1024 MiB
配点 : 1000 点
問題文
(1,2,\dots,N) の順列 Q と非負整数 k に対して、以下のように (1,2,\dots,N) の順列 Q^k を定めます。
- 数列 R=(1,2,\dots,N) に対して、以下の操作を k 回行って得られる R を Q^k とする。
- i = 1,2,\dots,N に対して、R_i を Q_{R_i} で置き換える。
(1,2,\dots,N) の順列が M 個与えられます。i 個目の順列は P_i = (P_{i,1},P_{i,2},\dots,P_{i,N}) です。
以下の条件を満たす (1,2,\dots,N) の順列 Q=(Q_1,Q_2,\dots,Q_N) が存在するか判定し、存在する場合は一つ求めてください。
- 1 \le i \le M を満たす全ての整数 i に対して、P_i = Q^k となる非負整数 k が存在する。
T 個のテストケースが与えられるので、それぞれについて解いてください。
制約
- 1 \le T \le 250000
- 1 \le N,M \le 500
- P_1,P_2,\dots,P_M は (1,2,\dots,N) の順列
- 全てのテストケースに対する NM の総和は 250000 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる。
N M
P_{1,1}\ P_{1,2}\ \dots\ P_{1,N}
P_{2,1}\ P_{2,2}\ \dots\ P_{2,N}
\vdots
P_{M,1}\ P_{M,2}\ \dots\ P_{M,N}
出力
T 行出力せよ。i 行目には \mathrm{case}_i の答えを以下の形式で出力せよ。
条件を満たす Q が存在しないならば -1 を出力せよ。存在するならば以下の形式で出力せよ。
Q_1\ Q_2\ \dots\ Q_N
条件を満たす Q が複数存在する場合、どれを出力しても正解とみなされる。
入力例 1
6 3 2 2 3 1 3 1 2 3 2 2 3 1 1 3 2 5 2 1 5 2 4 3 4 2 3 1 5 5 1 4 2 5 1 3 9 4 2 9 7 5 4 3 8 1 6 3 7 2 5 4 1 9 6 8 3 7 2 4 5 1 9 6 8 7 8 9 4 5 2 6 3 1 10 4 9 2 1 4 5 6 8 3 7 10 7 4 9 5 10 2 3 1 8 6 3 4 8 5 10 2 9 7 1 6 1 10 3 6 2 5 7 8 9 4
出力例 1
3 1 2 -1 4 5 2 1 3 4 2 5 1 3 7 8 9 5 4 2 6 3 1 -1
1 番目のケースについては、例えば Q=(3,1,2) は条件を満たします。
Q^0 = (1,2,3),Q^1 = (3,1,2),Q^2 = (2,3,1) となるため、P_1 = Q^2,P_2 = Q^1 となり条件を満たします。
2 番目のケースについては、条件を満たす Q は存在しません。
Score : 1000 points
Problem Statement
For a permutation Q of (1,2,\dots,N) and a non-negative integer k, define a permutation Q^k of (1,2,\dots,N) as follows.
- Let Q^k be the sequence R=(1,2,\dots,N) obtained after performing the following operation k times.
- For i = 1,2,\dots,N, replace R_i with Q_{R_i}.
You are given M permutations of (1,2,\dots,N). The i-th permutation is P_i = (P_{i,1},P_{i,2},\dots,P_{i,N}).
Determine whether there exists a permutation Q=(Q_1,Q_2,\dots,Q_N) of (1,2,\dots,N) satisfying the following condition, and if it exists, find one such Q.
- For every integer i satisfying 1 \le i \le M, there exists a non-negative integer k such that P_i = Q^k.
You are given T test cases; solve each of them.
Constraints
- 1 \le T \le 250000
- 1 \le N,M \le 500
- P_1,P_2,\dots,P_M are permutations of (1,2,\dots,N).
- The sum of NM over all test cases is at most 250000.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N M
P_{1,1}\ P_{1,2}\ \dots\ P_{1,N}
P_{2,1}\ P_{2,2}\ \dots\ P_{2,N}
\vdots
P_{M,1}\ P_{M,2}\ \dots\ P_{M,N}
Output
Output T lines. The i-th line should contain the answer to \mathrm{case}_i in the following format.
If there is no Q satisfying the condition, output -1. If one exists, output it in the following format:
Q_1\ Q_2\ \dots\ Q_N
If there are multiple Q satisfying the condition, any of them will be accepted.
Sample Input 1
6 3 2 2 3 1 3 1 2 3 2 2 3 1 1 3 2 5 2 1 5 2 4 3 4 2 3 1 5 5 1 4 2 5 1 3 9 4 2 9 7 5 4 3 8 1 6 3 7 2 5 4 1 9 6 8 3 7 2 4 5 1 9 6 8 7 8 9 4 5 2 6 3 1 10 4 9 2 1 4 5 6 8 3 7 10 7 4 9 5 10 2 3 1 8 6 3 4 8 5 10 2 9 7 1 6 1 10 3 6 2 5 7 8 9 4
Sample Output 1
3 1 2 -1 4 5 2 1 3 4 2 5 1 3 7 8 9 5 4 2 6 3 1 -1
For the first case, for example, Q=(3,1,2) satisfies the condition.
Since Q^0 = (1,2,3),Q^1 = (3,1,2),Q^2 = (2,3,1), we have P_1 = Q^2,P_2 = Q^1, so the condition is satisfied.
For the second case, there is no Q satisfying the condition.
実行時間制限: 8 sec / メモリ制限: 1024 MiB
配点 : 1200 点
問題文
(1,2,\dots,N) の順列の組 (P,Q)=((P_1,P_2,\dots,P_N),(Q_1,Q_2,\dots,Q_N)) であって、以下の条件を満たすものの個数を 998244353 で割った余りを求めてください。
- 1 \le i \le N を満たす全ての整数 i に対して P_i \le i+M,Q_i \le i+M,P_i \neq Q_i を全て満たす。
制約
- 2 \le N \le 10^9
- 1 \le M \le 125000
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを出力せよ。
入力例 1
3 1
出力例 1
4
(P,Q) として条件を満たすものは、以下の 4 通りです。
- P = (1,2,3),Q = (2,3,1)
- P = (1,3,2),Q = (2,1,3)
- P = (2,3,1),Q = (1,2,3)
- P = (2,1,3),Q = (1,3,2)
入力例 2
7 3
出力例 2
644544
入力例 3
1000000000 125000
出力例 3
357543611
Score : 1200 points
Problem Statement
Find the number, modulo 998244353, of pairs of permutations (P,Q)=((P_1,P_2,\dots,P_N),(Q_1,Q_2,\dots,Q_N)) of (1,2,\dots,N) satisfying the following condition.
- P_i \le i+M, Q_i \le i+M, and P_i \neq Q_i all hold for every integer i satisfying 1 \le i \le N.
Constraints
- 2 \le N \le 10^9
- 1 \le M \le 125000
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
Output
Output the answer.
Sample Input 1
3 1
Sample Output 1
4
The pairs (P,Q) satisfying the condition are the following four pairs.
- P = (1,2,3),Q = (2,3,1)
- P = (1,3,2),Q = (2,1,3)
- P = (2,3,1),Q = (1,2,3)
- P = (2,1,3),Q = (1,3,2)
Sample Input 2
7 3
Sample Output 2
644544
Sample Input 3
1000000000 125000
Sample Output 3
357543611