C - Snuke Festival

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

りんごさんが作ることのできる祭壇は何種類あるでしょうか。ただし、2 つの祭壇が異なるとは、上部、中部、下部に使われるピースのうち 少なくとも 1 つが異なることを言います。

### 制約

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9(1\leq i\leq N)
• 1 \leq B_i \leq 10^9(1\leq i\leq N)
• 1 \leq C_i \leq 10^9(1\leq i\leq N)
• 入力は全て整数である

### 入力

N
A_1 ... A_N
B_1 ... B_N
C_1 ... C_N


### 出力

りんごさんが作ることのできる祭壇の種類数を出力せよ。

### 入力例 1

2
1 5
2 4
3 6


### 出力例 1

3


• 上部に 1 個目、中部に 1 個目、下部に 1 個目のパーツを使った祭壇
• 上部に 1 個目、中部に 1 個目、下部に 2 個目のパーツを使った祭壇
• 上部に 1 個目、中部に 2 個目、下部に 2 個目のパーツを使った祭壇

### 入力例 2

3
1 1 1
2 2 2
3 3 3


### 出力例 2

27


### 入力例 3

6
3 14 159 2 6 53
58 9 79 323 84 6
2643 383 2 79 50 288


### 出力例 3

87


Score : 300 points

### Problem Statement

The season for Snuke Festival has come again this year. First of all, Ringo will perform a ritual to summon Snuke. For the ritual, he needs an altar, which consists of three parts, one in each of the three categories: upper, middle and lower.

He has N parts for each of the three categories. The size of the i-th upper part is A_i, the size of the i-th middle part is B_i, and the size of the i-th lower part is C_i.

To build an altar, the size of the middle part must be strictly greater than that of the upper part, and the size of the lower part must be strictly greater than that of the middle part. On the other hand, any three parts that satisfy these conditions can be combined to form an altar.

How many different altars can Ringo build? Here, two altars are considered different when at least one of the three parts used is different.

### Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9(1\leq i\leq N)
• 1 \leq B_i \leq 10^9(1\leq i\leq N)
• 1 \leq C_i \leq 10^9(1\leq i\leq N)
• All input values are integers.

### Input

Input is given from Standard Input in the following format:

N
A_1 ... A_N
B_1 ... B_N
C_1 ... C_N


### Output

Print the number of different altars that Ringo can build.

### Sample Input 1

2
1 5
2 4
3 6


### Sample Output 1

3


The following three altars can be built:

• Upper: 1-st part, Middle: 1-st part, Lower: 1-st part
• Upper: 1-st part, Middle: 1-st part, Lower: 2-nd part
• Upper: 1-st part, Middle: 2-nd part, Lower: 2-nd part

### Sample Input 2

3
1 1 1
2 2 2
3 3 3


### Sample Output 2

27


### Sample Input 3

6
3 14 159 2 6 53
58 9 79 323 84 6
2643 383 2 79 50 288


### Sample Output 3

87

D - Small Multiple

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

K の正の倍数の 10 進法での各桁の和としてありうる最小の値を求めてください。

### 制約

• 2 \leq K \leq 10^5
• K は整数である

### 入力

K


### 出力

K の倍数の 10 進法での各桁の和としてありうる最小の値を出力せよ。

### 入力例 1

6


### 出力例 1

3


12=6×2 が最小値を達成します。

### 入力例 2

41


### 出力例 2

5


11111=41×271 が最小値を達成します。

### 入力例 3

79992


### 出力例 3

36


Score : 700 points

### Problem Statement

Find the smallest possible sum of the digits in the decimal notation of a positive multiple of K.

### Constraints

• 2 \leq K \leq 10^5
• K is an integer.

### Input

Input is given from Standard Input in the following format:

K


### Output

Print the smallest possible sum of the digits in the decimal notation of a positive multiple of K.

### Sample Input 1

6


### Sample Output 1

3


12=6×2 yields the smallest sum.

### Sample Input 2

41


### Sample Output 2

5


11111=41×271 yields the smallest sum.

### Sample Input 3

79992


### Sample Output 3

36

E - Finite Encyclopedia of Integer Sequences

Time Limit: 2 sec / Memory Limit: 256 MB

### 制約

• 1 \leq K,N \leq 3 × 10^5
• N,K は整数である

### 入力

K N


### 入力例 1

3 2


### 出力例 1

2 1


### 入力例 2

2 4


### 出力例 2

1 2 2 2


### 入力例 3

5 14


### 出力例 3

3 3 3 3 3 3 3 3 3 3 3 3 2 2


Score : 800 points

### Problem Statement

In Finite Encyclopedia of Integer Sequences (FEIS), all integer sequences of lengths between 1 and N (inclusive) consisting of integers between 1 and K (inclusive) are listed.

Let the total number of sequences listed in FEIS be X. Among those sequences, find the (X/2)-th (rounded up to the nearest integer) lexicographically smallest one.

### Constraints

• 1 \leq N,K \leq 3 × 10^5
• N and K are integers.

### Input

Input is given from Standard Input in the following format:

K N


### Output

Print the (X/2)-th (rounded up to the nearest integer) lexicographically smallest sequence listed in FEIS, with spaces in between, where X is the total number of sequences listed in FEIS.

### Sample Input 1

3 2


### Sample Output 1

2 1


There are 12 sequences listed in FEIS: (1),(1,1),(1,2),(1,3),(2),(2,1),(2,2),(2,3),(3),(3,1),(3,2),(3,3). The (12/2 = 6)-th lexicographically smallest one among them is (2,1).

### Sample Input 2

2 4


### Sample Output 2

1 2 2 2


### Sample Input 3

5 14


### Sample Output 3

3 3 3 3 3 3 3 3 3 3 3 3 2 2

F - XorShift

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

• 黒板に書かれている整数を 1 つ選び、その整数の 2 倍の整数を新たに書き加える。選ばれた整数も、そのまま残しておく。
• 黒板に書かれている相異なるとは限らない整数を 2 つ選び、その 2 整数の bitwise xor を新たに書き加える。選ばれた整数も、そのまま残しておく。

### 制約

• 1 \leq N \leq 6
• 1 \leq X < 2^{4000}
• 1 \leq A_i < 2^{4000}(1\leq i\leq N)
• 入力は全て整数である
• X,A_i(1\leq i\leq N)2 進表記で与えられ、先頭の桁は 1 である

### 入力

N X
A_1
:
A_N


### 入力例 1

3 111
1111
10111
10010


### 出力例 1

4


• 152 倍し、30 を書く
• 3018 の xor をとり、12 を書く
• 122 倍し、24 を書く
• 3024 の xor をとり、6 を書く

### 入力例 2

4 100100
1011
1110
110101
1010110


### 出力例 2

37


### 入力例 3

4 111001100101001
10111110
1001000110
100000101
11110000011


### 出力例 3

1843


### 入力例 4

1 111111111111111111111111111111111111111111111111111111111111111
1


### 出力例 4

466025955


998244353 で割った余りを求めてください。

Score : 1000 points

### Problem Statement

There are N non-negative integers written on a blackboard. The i-th integer is A_i.

Takahashi can perform the following two kinds of operations any number of times in any order:

• Select one integer written on the board (let this integer be X). Write 2X on the board, without erasing the selected integer.
• Select two integers, possibly the same, written on the board (let these integers be X and Y). Write X XOR Y (XOR stands for bitwise xor) on the blackboard, without erasing the selected integers.

How many different integers not exceeding X can be written on the blackboard? We will also count the integers that are initially written on the board. Since the answer can be extremely large, find the count modulo 998244353.

### Constraints

• 1 \leq N \leq 6
• 1 \leq X < 2^{4000}
• 1 \leq A_i < 2^{4000}(1\leq i\leq N)
• All input values are integers.
• X and A_i(1\leq i\leq N) are given in binary notation, with the most significant digit in each of them being 1.

### Input

Input is given from Standard Input in the following format:

N X
A_1
:
A_N


### Output

Print the number of different integers not exceeding X that can be written on the blackboard.

### Sample Input 1

3 111
1111
10111
10010


### Sample Output 1

4


Initially, 15, 23 and 18 are written on the blackboard. Among the integers not exceeding 7, four integers, 0, 3, 5 and 6, can be written. For example, 6 can be written as follows:

• Double 15 to write 30.
• Take XOR of 30 and 18 to write 12.
• Double 12 to write 24.
• Take XOR of 30 and 24 to write 6.

### Sample Input 2

4 100100
1011
1110
110101
1010110


### Sample Output 2

37


### Sample Input 3

4 111001100101001
10111110
1001000110
100000101
11110000011


### Sample Output 3

1843


### Sample Input 4

1 111111111111111111111111111111111111111111111111111111111111111
1


### Sample Output 4

466025955


Be sure to find the count modulo 998244353.