AtCoder Regular Contest 133

A - Erase by Value

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

長さ N の整数列 A=(A_1,A_2,\cdots,A_N) が与えられます．

すぬけくんは今から， A の中から一つ値を選びます．ここで選んだ値を x とします．そして，A の要素のうち，x でないものを元の順番を保ったまま並べ，整数列 a を作ります．

a としてありうる数列のうち，辞書順最小のものを求めてください．

制約

1 \leq N \leq 200000
1 \leq A_i \leq N
入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

N
A_1 A_2 \cdots A_N

出力

辞書順最小の a の要素を空白区切りで出力せよ．

入力例 1

5
2 4 4 1 2

出力例 1

2 1 2

例えば，x=2 とすると，a=(4,4,1) となります．また，x=4 とすると，a=(2,1,2) となり，これは辞書順最小です．

入力例 2

3
1 1 1

出力例 2

x=1 とすると a は空になり，これは明らかに辞書順最小です．なお，出力に余計な空白や改行が含まれていても構いません．

入力例 3

5
1 1 2 3 3

出力例 3

1 1 2

Score : 300 points

Problem Statement

Given is a sequence of N integers A=(A_1,A_2,\cdots,A_N).

Snuke now chooses a value in A. Let x be the value chosen. Then, he makes an integer sequence a by lining up all elements of A that are not x without changing the order.

Find the lexicographically smallest sequence that can be obtained as a.

Constraints

1 \leq N \leq 200000
1 \leq A_i \leq N
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the elements of the lexicographically smallest a, separated by spaces.

Sample Input 1

5
2 4 4 1 2

Sample Output 1

2 1 2

For example, when x=2, we will have a=(4,4,1). When x=4, we will have a=(2,1,2), which is the lexicographically smallest.

Sample Input 2

3
1 1 1

Sample Output 2

When x=1, a will be empty, which is obviously the lexicographically smallest. As a side note, the output may contain additional spaces or newlines.

Sample Input 3

5
1 1 2 3 3

Sample Output 3

1 1 2

B - Dividing Subsequence

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

(1,2,\cdots,N) の順列 P=(P_1,P_2,\cdots,P_N) および Q=(Q_1,Q_2,\cdots,Q_N) が与えられます．

すぬけくんは，P と Q から（連続するとは限らない）部分列を取り出そうとしています．ここで，取り出した部分列は以下の条件を満たす必要があります．

P から取り出した部分列と Q から取り出した部分列の長さは等しい．以下，この長さを k とおく．
P から取り出した部分列を a=(a_1,a_2,\cdots,a_k)，Q から取り出した部分列を b=(b_1,b_2,\cdots,b_k) とおく．このとき，各 1 \leq i \leq k について，b_i は a_i の倍数である．

すぬけ君が取り出せる部分列の長さの最大値を求めて下さい．

制約

1 \leq N \leq 200000
P は (1,2,\cdots,N) の順列である
Q は (1,2,\cdots,N) の順列である
入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

N
P_1 P_2 \cdots P_N
Q_1 Q_2 \cdots Q_N

出力

答えを出力せよ．

入力例 1

4
3 1 4 2
4 2 1 3

出力例 1

P から部分列 (1,2) を，Q から部分列 (4,2) を取り出すと，これは条件を満たします．長さ 3 以上の部分列を条件を満たすように取ることはできないため，答えは 2 です．

入力例 2

5
1 2 3 4 5
5 4 3 2 1

出力例 2

入力例 3

10
4 3 1 10 9 2 8 6 5 7
9 6 5 4 2 3 8 10 1 7

出力例 3

Score : 500 points

Problem Statement

Given are permutations P=(P_1,P_2,\cdots,P_N) and Q=(Q_1,Q_2,\cdots,Q_N) of (1,2,\cdots,N).

Snuke is going to extract (not necessarily contiguous) subsequences from P and Q. Here, the subsequences must satisfy the conditions below.

The length of the subsequence extracted from P and that extracted from Q are the same. Below, let k be this length.
Let a=(a_1,a_2,\cdots,a_k) and b=(b_1,b_2,\cdots,b_k) be the subsequences extracted from P and Q, respectively. Then, for each 1 \leq i \leq k, b_i is a multiple of a_i.

Find the maximum possible length of each subsequence extracted by Snuke.

Constraints

1 \leq N \leq 200000
P is a permutation of (1,2,\cdots,N).
Q is a permutation of (1,2,\cdots,N).
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
P_1 P_2 \cdots P_N
Q_1 Q_2 \cdots Q_N

Output

Print the answer.

Sample Input 1

4
3 1 4 2
4 2 1 3

Sample Output 1

If we extract the subsequence (1,2) from P and (4,2) from Q, they satisfy the conditions. It is impossible to extract subsequences of length 3 or greater to satisfy the conditions, so the answer is 2.

Sample Input 2

5
1 2 3 4 5
5 4 3 2 1

Sample Output 2

Sample Input 3

10
4 3 1 10 9 2 8 6 5 7
9 6 5 4 2 3 8 10 1 7

Sample Output 3

C - Row Column Sums

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

H 行 W 列からなるマス目があります．

すぬけくんは，各マスに 0 以上 K-1 以下の整数を書き込もうとしています．ここで，以下の条件を満たす必要があります．

各 1 \leq i \leq H について，i 行目にあるマスに書かれた整数の総和を K で割った余りは A_i である．
各 1 \leq i \leq W について，i 列目にあるマスに書かれた整数の総和を K で割った余りは B_i である．

条件を満たすようにマスに整数を書き込むことができるかどうか判定し，また可能な場合は，書き込む整数の総和としてありうる最大値を求めてください．

制約

1 \leq H,W \leq 200000
2 \leq K \leq 200000
0 \leq A_i \leq K-1
0 \leq B_i \leq K-1
入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

H W K
A_1 A_2 \cdots A_H
B_1 B_2 \cdots B_W

出力

条件を満たすようにマスに整数を書き込むことが不可能な場合，-1 と出力せよ．可能な場合，書き込む整数の総和としてありうる最大値を出力せよ．

入力例 1

2 4 3
0 2
1 2 2 0

出力例 1

以下のように書き込めば良いです．

-----------------
| 2 | 0 | 2 | 2 |
-----------------
| 2 | 2 | 0 | 1 |
-----------------

この書き方は条件を満たしています．例えば 1 行目に書かれた整数の総和は 6 であり，これを K(=3) で割ったあまりは A_1(=0) になっています．

この書き方では整数の総和は 11 になっており，これはありうる最大値です．

入力例 2

3 3 4
0 1 2
1 2 3

出力例 2

-1

Score : 500 points

Problem Statement

We have a grid with H rows and W columns.

Snuke is going to write in each square an integer between 0 and K-1 (inclusive). Here, the conditions below must be satisfied.

For each 1 \leq i \leq H, the sum modulo K of the integers written in the i-th row is A_i.
For each 1 \leq i \leq W, the sum modulo K of the integers written in the i-th column is B_i.

Determine whether it is possible to write integers in the squares to satisfy the conditions. If it is possible, also find the maximum possible sum of the integers written.

Constraints

1 \leq H,W \leq 200000
2 \leq K \leq 200000
0 \leq A_i \leq K-1
0 \leq B_i \leq K-1
All values in input are integers.

Input

Input is given from Standard Input in the following format:

H W K
A_1 A_2 \cdots A_H
B_1 B_2 \cdots B_W

Output

If it is impossible to write integers in the squares to satisfy the conditions, print -1. If it is possible, print the maximum possible sum of the integers written.

Sample Input 1

2 4 3
0 2
1 2 2 0

Sample Output 1

The following should be written.

-----------------
| 2 | 0 | 2 | 2 |
-----------------
| 2 | 2 | 0 | 1 |
-----------------

We can see that the conditions are satisfied. For example, the sum of the integers in the 1-st row is 6, which modulo K(=3) is A_1(=0).

The sum of the integers written here is 11, which is the maximum possible value.

Sample Input 2

3 3 4
0 1 2
1 2 3

Sample Output 2

-1

D - Range XOR

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

整数 L,R,V が与えられます．次の条件を両方満たす整数の組 (l,r) の個数を 998244353 で割った余りを求めてください．

L \leq l \leq r \leq R
l \oplus (l+1) \oplus \cdots \oplus r=V

ただしここで，\oplus はビット単位 \mathrm{XOR} 演算を表します．

ビット単位 \mathrm{XOR} 演算とは

非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。

A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。

例えば、3 \oplus 5 = 6 となります (二進表記すると: 011 \oplus 101 = 110)。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots p_k の順番によらないことが証明できます。

制約

1 \leq L \leq R \leq 10^{18}
0 \leq V \leq 10^{18}
入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

L R V

出力

答えを出力せよ．

入力例 1

1 3 3

出力例 1

条件を満たすのは，(l,r)=(1,2) と (l,r)=(3,3) の 2 つです．

入力例 2

10 20 0

出力例 2

入力例 3

1 1 1

出力例 3

入力例 4

12345 56789 34567

出力例 4

Score : 700 points

Problem Statement

Given are integers L, R, and V. Find the number of pairs of integers (l,r) that satisfy both of the conditions below, modulo 998244353.

L \leq l \leq r \leq R
l \oplus (l+1) \oplus \cdots \oplus r=V

Here, \oplus denotes the bitwise \mathrm{XOR} operation.

What is bitwise \mathrm{XOR}?

The bitwise \mathrm{XOR} of non-negative integers A and B, A \oplus B, is defined as follows:

When A \oplus B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of A and B is 1, and 0 otherwise.

For example, we have 3 \oplus 5 = 6 (in base two: 011 \oplus 101 = 110).
Generally, the bitwise \mathrm{XOR} of k integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k). We can prove that this value does not depend on the order of p_1, p_2, p_3, \dots p_k.

Constraints

1 \leq L \leq R \leq 10^{18}
0 \leq V \leq 10^{18}
All values in input are integers.

Input

Input is given from Standard Input in the following format:

L R V

Output

Print the answer.

Sample Input 1

1 3 3

Sample Output 1

The two pairs satisfying the conditions are (l,r)=(1,2) and (l,r)=(3,3).

Sample Input 2

10 20 0

Sample Output 2

Sample Input 3

1 1 1

Sample Output 3

Sample Input 4

12345 56789 34567

Sample Output 4

E - Cyclic Medians

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

整数 N,M,V,A が与えられます．次のような操作を考えます．

1 以上 V 以下の整数からなる長さ N の整数列 x=(x_1,x_2,\cdots,x_N) を選ぶ．
1 以上 V 以下の整数からなる長さ M の整数列 y=(y_1,y_2,\cdots,y_M) を選ぶ．
変数 a を用意する．最初，a=A とする．
i=0,1,\cdots,N \times M-1 に対して，以下の動作を行う．
- a の値を，a,x_{(i \bmod N)+1},y_{(i \bmod M)+1} の中央値で置き換える．
最終的な a の値を出力する．

整数列 x,y としてありうるものをすべて試したとき，操作によって出力される値の総和を 998244353 で割った余りを求めてください．

制約

1 \leq N,M \leq 200000
1 \leq A \leq V \leq 200000
入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

N M V A

出力

答えを出力せよ．

入力例 1

2 1 2 1

出力例 1

例えば，x=(1,2),y=(2) の時，操作の様子は以下のようになります．

a=1 と初期化する．
i=1: a の値を，a(=1),x_1(=1),y_1(=2) の中央値，すなわち 1 で置き換える．
i=2: a の値を，a(=1),x_2(=2),y_1(=2) の中央値，すなわち 2 で置き換える．
a(=2) を出力．

最終的に 2 が出力されるのは，(x=(1,2),y=(2))，(x=(2,1),y=(2))，(x=(2,2),y=(2)) の 3 ケースで，それ以外の 5 ケースではすべて 1 が出力されます．よって求める答えは，2 \times 3 + 1\times 5=11 です．

入力例 2

2 2 5 4

出力例 2

入力例 3

2100 2300 2201 2022

出力例 3

407723438

Score : 800 points

Problem Statement

Given are integers N, M, V, and A. Consider the following procedure.

Choose a sequence of N integers between 1 and V (inclusive): x=(x_1,x_2,\cdots,x_N).
Choose a sequence of M integers between 1 and V (inclusive): y=(y_1,y_2,\cdots,y_M).
Let a be a variable and initialize it with a=A.
For each i=0,1,\cdots,N \times M-1, do the following.
- Replace the value of a with the median of a,x_{(i \bmod N)+1},y_{(i \bmod M)+1}.
Print the final value of a.

Consider doing this procedure with every possible pair of sequences x,y. Find the sum of the values that will be printed, modulo 998244353.

Constraints

1 \leq N,M \leq 200000
1 \leq A \leq V \leq 200000
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M V A

Output

Print the answer.

Sample Input 1

2 1 2 1

Sample Output 1

For example, when x=(1,2),y=(2), the procedure goes as follows.

Initialize a with a=1.
For i=1: replace the value of a with the median of a(=1),x_1(=1),y_1(=2), which is 1.
For i=2: replace the value of a with the median of a(=1),x_2(=2),y_1(=2), which is 2.
Print a(=2).

There are three cases where 2 will be printed: (x=(1,2),y=(2)), (x=(2,1),y=(2)), (x=(2,2),y=(2)). In the other five cases, 1 will be printed. Therefore, the answer is 2 \times 3 + 1\times 5=11.

Sample Input 2

2 2 5 4

Sample Output 2

Sample Input 3

2100 2300 2201 2022

Sample Output 3

407723438

F - Random Transition

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 1100 点

問題文

整数 N が与えられます．

すぬけくんはこれから，以下の操作を行います．

変数 x を用意し，ランダムに選んだ 0 以上 N 以下の整数で初期化する．各 0 \leq i \leq N に対し，x=i と初期化する確率は A_i/10^9 である．
次の操作を K 回繰り返す．
- 確率 x/N で x の値を 1 減らし，確率 1-x/N で x の値を 1 増やす．（ここで，操作後も x の値が必ず 0 以上 N 以下であることに注意）

各 i=0,1,\cdots,N について，すべての操作が終了したあとに x=i である確率を \pmod{998244353} で求めてください．

確率 \pmod{998244353} の定義

求める確率は必ず有理数になることが証明できます。また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \neq 0 \pmod{998244353} となることも証明できます。よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります。この R を答えてください。

制約

1 \leq N \leq 100000
0 \leq A_i
\sum_{0 \leq i \leq N}A_i = 10^9
1 \leq K \leq 10^9
入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

N K
A_0 A_1 \cdots A_N

出力

各 i=0,1,\cdots,N について，すべての操作が終了したあとに x=i である確率を \pmod{998244353} で出力せよ．

入力例 1

2 1
0 1000000000 0

出力例 1

499122177 0 499122177

最初は必ず x=1 と初期化します．その後の操作では．確率 1/2 で x の値を 1 減らし，確率 1/2 で x の値を 1 増やします．最終的に x=0,1,2 となる確率は，それぞれ 1/2,0,1/2 です．

入力例 2

4 2
200000000 200000000 200000000 200000000 200000000

出力例 2

723727156 598946612 349385524 598946612 723727156

入力例 3

10 100
21265166 263511538 35931763 26849698 108140810 134702248 36774526 147099145 58335759 4118743 163270604

出力例 3

505314898 24510700 872096939 107940764 808162829 831195162 314651262 535843032 665830283 627881537 696038713

Score : 1100 points

Problem Statement

Given is an integer N.

Snuke is going to do the procedure below.

Let x be a variable and initialize it with a random integer between 0 and N (inclusive). For each 0 \leq i \leq N, x=i is chosen with probability A_i/10^9.
Repeat the following operation K times.
- With probability x/N, decrease the value of x by 1; with probability 1-x/N, increase it by 1. (Here, note that x will still be between 0 and N after the operation.)

For each i=0,1,\cdots,N, find the probability, modulo 998244353, that x=i after the procedure.

Definition of probability modulo 998244353

It can be proved that the sought probabilities are always rational numbers. Additionally, under the Constraints of this problem, when representing each of them as an irreducible fraction \frac{P}{Q}, it can be proved that Q \neq 0 \pmod{998244353}. Thus, there uniquely exists an integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Answer with this R.

Constraints

1 \leq N \leq 100000
0 \leq A_i
\sum_{0 \leq i \leq N}A_i = 10^9
1 \leq K \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_0 A_1 \cdots A_N

Output

For each i=0,1,\cdots,N, print the probability, modulo 998244353, that x=i after the procedure.

Sample Input 1

2 1
0 1000000000 0

Sample Output 1

499122177 0 499122177

First, x is always initialized with x=1. In the subsequent operation, the value of x is decreased by 1 with probability 1/2 and increased by 1 with probability 1/2. Eventually, we will have x=0,1,2 with probabilities 1/2,0,1/2, respectively.

Sample Input 2

4 2
200000000 200000000 200000000 200000000 200000000

Sample Output 2

723727156 598946612 349385524 598946612 723727156

Sample Input 3

10 100
21265166 263511538 35931763 26849698 108140810 134702248 36774526 147099145 58335759 4118743 163270604

Sample Output 3

505314898 24510700 872096939 107940764 808162829 831195162 314651262 535843032 665830283 627881537 696038713