実行時間制限: 4 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
N \times N のマス目があります。上から i 行目、左から j 列目のマスを (i,j) と呼びます。
これから各マスに 0 か 1 を書き込みます。以下の条件を全て満たすように書き込む方法を一つ構築してください。
- M 個のマス (A_1,B_1),(A_2,B_2),\dots,(A_M,B_M) には 1 が書かれている。
- i 行目のマスに書かれた整数の総和は M である。(1 \le i \le N)
- i 列目のマスに書かれた整数の総和は M である。(1 \le i \le N)
本問題の制約下で、条件を満たす書き込み方が存在することが証明出来ます。
制約
- 1 \le N \le 10^5
- 1 \le M \le \min(N,10)
- 1 \le A_i,B_i \le N
- i \neq j ならば (A_i,B_i) \neq (A_j,B_j)
入力
入力は以下の形式で標準入力から与えられる。
N M
A_1 B_1
A_2 B_2
\vdots
A_{M} B_{M}
出力
1 を書き込むマスをマス (x_1,y_1),(x_2,y_2),\dots,(x_k,y_k) としたとき、以下のように出力せよ。
k x_1 y_1 x_2 y_2 \vdots x_k y_k
なお、条件を満たす書き込み方が複数存在する場合その中のどれを出力しても正答となる。
入力例 1
4 2 1 4 3 2
出力例 1
8 1 2 1 4 2 1 2 4 3 2 3 3 4 1 4 3
この出力では、マス目に以下のように整数を書き込んでいます。全ての条件を満たしているので、この出力は正答です。
0101 1001 0110 1010
入力例 2
3 3 3 1 2 3 1 3
出力例 2
9 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
入力例 3
7 3 1 7 7 6 6 1
出力例 3
21 1 6 2 4 4 1 7 3 3 6 4 5 6 1 1 7 7 6 3 5 2 2 6 3 6 7 5 4 5 2 2 5 5 3 1 4 7 1 4 7 3 2
Score: 400 points
Problem Statement
There is an N \times N grid. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.
You are to fill each cell with 0 or 1. Construct one method to fill the grid that satisfies all of the following conditions:
- The cells (A_1,B_1), (A_2,B_2), \dots, (A_M,B_M) contain 1.
- The integers in the i-th row sum to M. (1 \le i \le N)
- The integers in the i-th column sum to M. (1 \le i \le N)
It can be proved that under the constraints of this problem, there is at least one method to fill the grid that satisfies the conditions.
Constraints
- 1 \le N \le 10^5
- 1 \le M \le \min(N,10)
- 1 \le A_i, B_i \le N
- (A_i, B_i) \neq (A_j, B_j) if i \neq j.
Input
The input is given from Standard Input in the following format:
N M
A_1 B_1
A_2 B_2
\vdots
A_{M} B_{M}
Output
Let (x_1,y_1), (x_2,y_2), \dots, (x_k,y_k) be the cells that contain 1, and print the following:
k x_1 y_1 x_2 y_2 \vdots x_k y_k
If multiple methods satisfy the conditions, any of them will be considered correct.
Sample Input 1
4 2 1 4 3 2
Sample Output 1
8 1 2 1 4 2 1 2 4 3 2 3 3 4 1 4 3
This output fills the grid as follows. All the conditions are satisfied, so this output is correct.
0101 1001 0110 1010
Sample Input 2
3 3 3 1 2 3 1 3
Sample Output 2
9 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
Sample Input 3
7 3 1 7 7 6 6 1
Sample Output 3
21 1 6 2 4 4 1 7 3 3 6 4 5 6 1 1 7 7 6 3 5 2 2 6 3 6 7 5 4 5 2 2 5 5 3 1 4 7 1 4 7 3 2
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
2^N を 2^M - 2^K で割ったあまりの 1 の位を求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1 \le T \le 2 \times 10^5
- 1 \le N \le 10^{18}
- 1 \le K < M \le 10^{18}
- N,M,K は整数
入力
入力は以下の形式で標準入力から与えられる。ここで、\mathrm{case}_i は i 番目のテストケースを意味する。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる。
N M K
出力
答えを出力せよ。
入力例 1
5 9 6 2 123 84 50 95 127 79 1000000007 998244353 924844033 473234053352300580 254411431220543632 62658522328486675
出力例 1
2 8 8 8 4
1 個目のテストケースについて、2^9 を 2^6 - 2^2 で割ったあまりは 32 です。よって 32 の 1 の位の 2 が答えです。
Score : 400 points
Problem Statement
Find the last digit of the remainder when 2^N is divided by 2^M - 2^K.
You are given T test cases, each of which must be solved.
Constraints
- 1 \le T \le 2 \times 10^5
- 1 \le N \le 10^{18}
- 1 \le K < M \le 10^{18}
- N,M,K are integers.
Input
The input is given from Standard Input in the following format, where \mathrm{case}_i represents the i-th test case:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N M K
Output
Print the answer.
Sample Input 1
5 9 6 2 123 84 50 95 127 79 1000000007 998244353 924844033 473234053352300580 254411431220543632 62658522328486675
Sample Output 1
2 8 8 8 4
For the first test case, the remainder of 2^9 divided by 2^6 - 2^2 is 32. Thus, the answer is the last digit of 32, which is 2.
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 700 点
問題文
(1,2,\dots,N) の順列 P=(P_1,P_2,\dots,P_N) のうち、以下の条件を全て満たすものの個数を 998244353 で割ったあまりを出力してください。
- \max(P_{A_i},P_{B_i}) = C_i\ (1 \le i \le M)
制約
- 2 \le N \le 2 \times 10^5
- 1 \le M \le 2 \times 10^5
- 1 \le A_i < B_i \le N
- 1 \le C_i \le N
- i \neq j ならば (A_i,B_i) \neq (A_j,B_j)
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M
出力
答えを出力せよ。
入力例 1
4 2 1 2 4 2 3 2
出力例 1
2
条件を満たす P は (4,1,2,3),(4,2,1,3) の 2 個です。
入力例 2
6 3 1 4 3 2 5 6 3 4 2
出力例 2
8
入力例 3
20 17 9 16 13 5 14 20 15 20 14 5 13 17 18 20 14 14 20 20 6 13 11 12 16 19 2 15 10 6 17 11 7 18 7 8 18 12 8 16 13 6 16 13 2 18 10 9 10 15 7 14 20
出力例 3
1209600
Score: 700 points
Problem Statement
Print the number, modulo 998244353, of permutations P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N) that satisfy all of the following conditions:
- \max(P_{A_i},P_{B_i}) = C_i\ (1 \le i \le M).
Constraints
- 2 \le N \le 2 \times 10^5
- 1 \le M \le 2 \times 10^5
- 1 \le A_i < B_i \le N
- 1 \le C_i \le N
- (A_i,B_i) \neq (A_j,B_j) if i \neq j.
Input
The input is given from Standard Input in the following format:
N M A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M
Output
Print the answer.
Sample Input 1
4 2 1 2 4 2 3 2
Sample Output 1
2
The two permutations P that satisfy the conditions are (4,1,2,3) and (4,2,1,3).
Sample Input 2
6 3 1 4 3 2 5 6 3 4 2
Sample Output 2
8
Sample Input 3
20 17 9 16 13 5 14 20 15 20 14 5 13 17 18 20 14 14 20 20 6 13 11 12 16 19 2 15 10 6 17 11 7 18 7 8 18 12 8 16 13 6 16 13 2 18 10 9 10 15 7 14 20
Sample Output 3
1209600
実行時間制限: 4 sec / メモリ制限: 1024 MB
配点 : 700 点
問題文
(1,2,\dots,N) の順列 P=(P_1,P_2,\dots,P_N) が与えられます。これから以下の操作を M 回行います。
- 1 \le i < j \le N を満たす整数の組 (i,j) を選び、P_i と P_j を入れ替える。
操作列は \left(\frac{N(N-1)}{2}\right)^M 通りありますが、その全てに対する操作終了時の \sum_{i=1}^{N-1} |P_i - P_{i+1}| の総和を 998244353 で割ったあまりを求めてください。
制約
- 2 \le N \le 2 \times 10^5
- 1 \le M \le 2 \times 10^5
- (P_1,P_2,\dots,P_N) は (1,2,\dots,N) の順列
入力
入力は以下の形式で標準入力から与えられる。
N M P_1 P_2 \dots P_N
出力
答えを出力せよ。
入力例 1
3 1 1 3 2
出力例 1
8
操作列としてあり得るものは以下の 3 通りです。
- (i,j) = (1,2) を選ぶ。P=(3,1,2) となる。
- (i,j) = (1,3) を選ぶ。P=(2,3,1) となる。
- (i,j) = (2,3) を選ぶ。P=(1,2,3) となる。
それぞれの \sum_{i=1}^{N-1} |P_i - P_{i+1}| は 3,3,2 です。よって答えは 3 + 3 + 2 = 8 です。
入力例 2
2 5 2 1
出力例 2
1
入力例 3
5 2 3 5 1 4 2
出力例 3
833
入力例 4
20 24 14 1 20 6 11 3 19 2 7 10 9 18 13 12 17 8 15 5 4 16
出力例 4
203984325
Score: 700 points
Problem Statement
You are given a permutation P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N). You will perform the following operation M times:
- Choose a pair of integers (i, j) such that 1 \le i < j \le N, and swap P_i and P_j.
There are \left(\frac{N(N-1)}{2}\right)^M possible sequences of operations. For each of them, consider the value \sum_{i=1}^{N-1} |P_i - P_{i+1}| after all the operations. Find the sum, modulo 998244353, of all those values.
Constraints
- 2 \le N \le 2 \times 10^5
- 1 \le M \le 2 \times 10^5
- (P_1,P_2,\dots,P_N) is a permutation of (1,2,\dots,N).
Input
The input is given from Standard Input in the following format:
N M P_1 P_2 \dots P_N
Output
Print the answer.
Sample Input 1
3 1 1 3 2
Sample Output 1
8
There are three possible sequences of operations:
- Choose (i,j) = (1,2), making P=(3,1,2).
- Choose (i,j) = (1,3), making P=(2,3,1).
- Choose (i,j) = (2,3), making P=(1,2,3).
The values of \sum_{i=1}^{N-1} |P_i - P_{i+1}| for these cases are 3, 3, 2, respectively. Thus, the answer is 3 + 3 + 2 = 8.
Sample Input 2
2 5 2 1
Sample Output 2
1
Sample Input 3
5 2 3 5 1 4 2
Sample Output 3
833
Sample Input 4
20 24 14 1 20 6 11 3 19 2 7 10 9 18 13 12 17 8 15 5 4 16
Sample Output 4
203984325
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 800 点
問題文
長さ N の正整数列 X=(X_1,X_2,\dots,X_N),Y=(Y_1,Y_2,\dots,Y_N) が与えられます。
また、長さ N の正整数列が M 個与えられます。i 個目の正整数列は A_i = (A_{i,1},A_{i,2},\dots,A_{i,N}) です。
あなたは i = 1,2,\dots,M の順に以下の操作のうちどちらかを行います。どちらを選ぶかは各 i に対して独立に決めることが出来ます。
- 1 \le j \le N を満たす全ての整数 j に対して X_j を \max(X_j,A_{i,j}) に置き換える。
- 1 \le j \le N を満たす全ての整数 j に対して Y_j を \max(Y_j,A_{i,j}) に置き換える。
操作終了時の \sum_{j=1}^{N} (X_j + Y_j) の最小値を求めてください。
制約
- 1 \le N \le 10
- 1 \le M \le 500
- 1 \le X_j,Y_j,A_{i,j} \le 500
入力
入力は以下の形式で標準入力から与えられる。
N M
X_1 X_2 \dots X_N
Y_1 Y_2 \dots Y_N
A_{1,1} A_{1,2} \dots A_{1,N}
A_{2,1} A_{2,2} \dots A_{2,N}
\vdots
A_{M,1} A_{M,2} \dots A_{M,N}
出力
答えを出力せよ。
入力例 1
3 2 4 4 2 3 1 5 2 5 2 1 2 4
出力例 1
21
最適な操作列の一例として、以下のようなものがあります。
- X_j を \max(X_j,A_{1,j}) に置き換える。X=(4,5,2) となる。
- Y_j を \max(Y_j,A_{2,j}) に置き換える。Y=(3,2,5) となる。
このように操作をすると、\sum_{j=1}^{N} (X_j + Y_j) = 21 が達成できます。
入力例 2
3 5 4 13 10 14 9 4 4 6 4 13 18 16 8 13 5 7 18 17 20 20 14
出力例 2
84
入力例 3
5 12 330 68 248 387 491 295 366 376 262 192 280 121 17 168 455 288 179 210 378 490 150 275 165 264 287 66 331 207 282 367 303 215 456 214 18 227 326 103 443 427 395 57 107 350 227 318 231 146 2 116 57 325 124 383 260 147 319 23 177 445 254 198 32 85 56 68 177 356 41 471
出力例 3
3595
Score: 800 points
Problem Statement
You are given two length-N sequences of positive integers: X=(X_1,X_2,\dots,X_N) and Y=(Y_1,Y_2,\dots,Y_N).
Additionally, you are given M length-N sequences of positive integers. The i-th sequence is A_i = (A_{i,1},A_{i,2},\dots,A_{i,N}).
For each i = 1,2,\dots,M, you must perform one of the following operations. You can independently choose which operation to perform for each i.
- Replace X_j with \max(X_j,A_{i,j}) for all integers j such that 1 \le j \le N.
- Replace Y_j with \max(Y_j,A_{i,j}) for all integers j such that 1 \le j \le N.
Find the minimum possible value of \sum_{j=1}^{N} (X_j + Y_j) after all operations.
Constraints
- 1 \le N \le 10
- 1 \le M \le 500
- 1 \le X_j, Y_j, A_{i,j} \le 500
Input
The input is given from Standard Input in the following format:
N M
X_1 X_2 \dots X_N
Y_1 Y_2 \dots Y_N
A_{1,1} A_{1,2} \dots A_{1,N}
A_{2,1} A_{2,2} \dots A_{2,N}
\vdots
A_{M,1} A_{M,2} \dots A_{M,N}
Output
Print the answer.
Sample Input 1
3 2 4 4 2 3 1 5 2 5 2 1 2 4
Sample Output 1
21
One optimal sequence of operations is as follows:
- Replace X_j with \max(X_j,A_{1,j}), making X = (4,5,2).
- Replace Y_j with \max(Y_j,A_{2,j}), making Y = (3,2,5).
This sequence of operations achieves \sum_{j=1}^{N} (X_j + Y_j) = 21.
Sample Input 2
3 5 4 13 10 14 9 4 4 6 4 13 18 16 8 13 5 7 18 17 20 20 14
Sample Output 2
84
Sample Input 3
5 12 330 68 248 387 491 295 366 376 262 192 280 121 17 168 455 288 179 210 378 490 150 275 165 264 287 66 331 207 282 367 303 215 456 214 18 227 326 103 443 427 395 57 107 350 227 318 231 146 2 116 57 325 124 383 260 147 319 23 177 445 254 198 32 85 56 68 177 356 41 471
Sample Output 3
3595
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 1000 点
問題文
頂点に 0 から NM の番号がついている NM+1 頂点の木があります。i(1 \le i \le NM) 本目の辺は頂点 i と頂点 \max(i-N,0) を結ぶ辺です。
最初、頂点 i は色 i \bmod N で塗られています。あなたは以下の操作を 0 回以上行うことが出来ます。
- 辺で結ばれている 2 頂点 u,v を選ぶ。u の色を v の色に塗り替える。
操作後の木としてあり得るものの個数を 998244353 で割ったあまりを求めてください。ただし、2 つの木はある頂点の色が違うときに区別します。
制約
- 1 \le N,M \le 2 \times 10^5
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを出力せよ。
入力例 1
3 1
出力例 1
42
例えば、操作列として以下のようなものが考えられます。このケースを含め、最終的にあり得る木としては 42 通りがあります。
入力例 2
4 2
出力例 2
219100
入力例 3
20 24
出力例 3
984288778
入力例 4
123456 112233
出力例 4
764098676
Score: 1000 points
Problem Statement
There is a tree with NM+1 vertices numbered 0 to NM. The i-th edge (1 \le i \le NM) connects vertices i and \max(i-N,0).
Initially, vertex i is colored with color i \bmod N. You can perform the following operation zero or more times:
- Choose two vertices u and v connected by an edge. Repaint the color of vertex u with that of vertex v.
Find the number, modulo 998244353, of possible trees after the operations. Two trees are distinguished if and only if some vertex has different colors.
Constraints
- 1 \le N, M \le 2 \times 10^5
Input
The input is given from Standard Input in the following format:
N M
Output
Print the answer.
Sample Input 1
3 1
Sample Output 1
42
One possible sequence of operations is as follows. Including this one, there are 42 possible final trees.
Sample Input 2
4 2
Sample Output 2
219100
Sample Input 3
20 24
Sample Output 3
984288778
Sample Input 4
123456 112233
Sample Output 4
764098676