AtCoder Regular Contest 144

A - Digit Sum of 2x

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

正整数 x に対して，その各桁の和を f(x) と表すことにします．例えば f(144) = 1+4+4 = 9，f(1)=1 です．

正整数 N が与えられます．次のように定まる正整数 M, x を求めてください．

f(x)=N かつ f(2x)=M を満たす正整数 x が存在するような，最大の正整数 M．
そのような M に対して，f(x)=N かつ f(2x)=M を満たす最小の正整数 x．

制約

1\leq N\leq 10^5

入力

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

出力

1 行目には M，2 行目には x を出力してください．

入力例 1

出力例 1

6
3

f(x)=3 であるとき必ず f(2x) = 6 となることが証明できます．したがって M=6 です． f(x)=3 かつ f(2x)=6 となる最小の正整数は x=3 です．これらを出力します．

入力例 2

出力例 2

12
24

入力例 3

出力例 3

200
4444444444444444444444444

Score : 300 points

Problem Statement

For a positive integer x, let f(x) be the sum of its digit. For example, f(144) = 1+4+4 = 9 and f(1)=1.

You are given a positive integer N. Find the following positive integers M and x:

The maximum positive integer M for which there exists a positive integer x such that f(x)=N and f(2x)=M.
The minimum positive integer x such that f(x)=N and f(2x)=M for the M above.

Constraints

1\leq N\leq 10^5

Input

Input is given from Standard Input in the following format:

Output

Print M in the first line and x in the second line.

Sample Input 1

Sample Output 1

6
3

We can prove that whenever f(x)=3, f(2x) = 6. Thus, M=6. The minimum positive integer x such that f(x)=3 and f(2x)=6 is x=3. These M and x should be printed.

Sample Input 2

Sample Output 2

12
24

Sample Input 3

Sample Output 3

200
4444444444444444444444444

B - Gift Tax

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

a\leq b を満たす正整数 a, b および，正整数列 A = (A_1, A_2, \ldots, A_N) が与えられます．

あなたはこの数列に対して，以下の操作を何度でも行うことができます（0 回でもよいです）：

相異なる添字 i, j (1\leq i, j \leq N) を選ぶ．A_i に a を加え，A_j から b を引く．

操作後の \min(A_1, A_2, \ldots, A_N) としてありうる最大値を求めてください．

制約

2\leq N\leq 3\times 10^5
1\leq a\leq b\leq 10^9
1\leq A_i\leq 10^{9}

入力

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

N a b
A_1 A_2 \ldots A_N

出力

操作後の \min(A_1, A_2, \ldots, A_N) としてありうる最大値を出力してください．

入力例 1

3 2 2
1 5 9

出力例 1

例えば次のように操作を行うことで， \min(A_1, A_2, A_3) = 5 を達成できます．

i = 1, j = 3 として操作を行う．A は (3, 5, 7) に変化する．
i = 1, j = 3 として操作を行う．A は (5, 5, 5) に変化する．

入力例 2

3 2 3
11 1 2

出力例 2

例えば次のように操作を行うことで， \min(A_1, A_2, A_3) = 3 を達成できます．

i = 1, j = 3 として操作を行う．A は (13, 1, -1) に変化する．
i = 2, j = 1 として操作を行う．A は (10, 3, -1) に変化する．
i = 3, j = 1 として操作を行う．A は (7, 3, 1) に変化する．
i = 3, j = 1 として操作を行う．A は (4, 3, 3) に変化する．

入力例 3

3 1 100
8 5 6

出力例 3

一度も操作を行わないことにより， \min(A_1, A_2, A_3) = 5 を達成できます．

入力例 4

6 123 321
10 100 1000 10000 100000 1000000

出力例 4

Score : 400 points

Problem Statement

You are given positive integers a and b such that a\leq b, and a sequence of positive integers A = (A_1, A_2, \ldots, A_N).

On this sequence, you can perform the following operation any number of times (possibly zero):

Choose distinct indices i, j (1\leq i, j \leq N). Add a to A_i and subtract b from A_j.

Find the maximum possible value of \min(A_1, A_2, \ldots, A_N) after your operations.

Constraints

2\leq N\leq 3\times 10^5
1\leq a\leq b\leq 10^9
1\leq A_i\leq 10^{9}

Input

Input is given from Standard Input in the following format:

N a b
A_1 A_2 \ldots A_N

Output

Print the maximum possible value of \min(A_1, A_2, \ldots, A_N) after your operations.

Sample Input 1

3 2 2
1 5 9

Sample Output 1

Here is one way to achieve \min(A_1, A_2, A_3) = 5.

Perform the operation with i = 1, j = 3. A becomes (3, 5, 7).
Perform the operation with i = 1, j = 3. A becomes (5, 5, 5).

Sample Input 2

3 2 3
11 1 2

Sample Output 2

Here is one way to achieve \min(A_1, A_2, A_3) = 3.

Perform the operation with i = 1, j = 3. A becomes (13, 1, -1).
Perform the operation with i = 2, j = 1. A becomes (10, 3, -1).
Perform the operation with i = 3, j = 1. A becomes (7, 3, 1).
Perform the operation with i = 3, j = 1. A becomes (4, 3, 3).

Sample Input 3

3 1 100
8 5 6

Sample Output 3

You can achieve \min(A_1, A_2, A_3) = 5 by not performing the operation at all.

Sample Input 4

6 123 321
10 100 1000 10000 100000 1000000

Sample Output 4

C - K Derangement

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

正整数 N, K が与えられます． 1 から N までの整数からなる順列 A = (A_1, A_2, \ldots, A_N) であって次の条件を満たすもののうち，辞書順最小のものを求めてください．

任意の i (1\leq i\leq N) に対して \lvert A_i - i\rvert \geq K が成り立つ．

そのような順列が存在しない場合には，-1 を出力してください．

数列の辞書順とは？

相異なる数列 S と数列 T の大小を判定するアルゴリズムを以下に説明します．

以下では S の i 番目の要素を S_i のように表します．また， S が T より辞書順で小さい場合は S \lt T ，大きい場合は S \gt T と表します．

S と T のうち長さが短い方の文字列の長さを L とします．i=1,2,\dots,L に対して S_i と T_i が一致するか調べます．
S_i \neq T_i である i が存在する場合，そのような i のうち最小のものを j とします．そして，S_j と T_j を比較して， S_j が T_j より（数として）小さい場合は S \lt T ，大きい場合は S \gt T と決定して，アルゴリズムを終了します．
S_i \neq T_i である i が存在しない場合， S と T の長さを比較して，S が T より短い場合は S \lt T ，長い場合は S \gt T と決定して，アルゴリズムを終了します．

制約

2\leq N\leq 3\times 10^5
1\leq K\leq N - 1

入力

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

N K

出力

条件を満たす順列 A のうち，辞書順最小のものを次の形式で出力してください．

A_1 A_2 \ldots A_N

そのような順列が存在しない場合には，-1 を出力してください．

入力例 1

3 1

出力例 1

2 3 1

条件を満たす順列は，(2, 3, 1) と (3, 1, 2) の 2 つです．例えば (2, 3, 1) は

\lvert A_1 - 1\rvert = 1 \geq K
\lvert A_2 - 2\rvert = 1 \geq K
\lvert A_3 - 3\rvert = 2 \geq K

であるため条件を満たしています．

入力例 2

8 3

出力例 2

4 5 6 7 8 1 2 3

入力例 3

8 6

出力例 3

-1

Score : 600 points

Problem Statement

You are given positive integers N and K. Find the lexicographically smallest permutation A = (A_1, A_2, \ldots, A_N) of the integers from 1 through N that satisfies the following condition:

\lvert A_i - i\rvert \geq K for all i (1\leq i\leq N).

If there is no such permutation, print -1.

What is lexicographical order on sequences?

The following is an algorithm to determine the lexicographical order between different sequences S and T.

Below, let S_i denote the i-th element of S. Also, if S is lexicographically smaller than T, we will denote that fact as S \lt T; if S is lexicographically larger than T, we will denote that fact as S \gt T.

Let L be the smaller of the lengths of S and T. For each i=1,2,\dots,L, we check whether S_i and T_i are the same.
If there is an i such that S_i \neq T_i, let j be the smallest such i. Then, we compare S_j and T_j. If S_j is less than T_j (as a number), we determine that S \lt T and quit; if S_j is greater than T_j, we determine that S \gt T and quit.
If there is no i such that S_i \neq T_i, we compare the lengths of S and T. If S is shorter than T, we determine that S \lt T and quit; if S is longer than T, we determine that S \gt T and quit.

Constraints

2\leq N\leq 3\times 10^5
1\leq K\leq N - 1

Input

Input is given from Standard Input in the following format:

N K

Output

Print the lexicographically smallest permutation A = (A_1, A_2, \ldots, A_N) of the integers from 1 through N that satisfies the condition, in the following format:

A_1 A_2 \ldots A_N

If there is no such permutation, print -1.

Sample Input 1

3 1

Sample Output 1

2 3 1

Two permutations satisfy the condition: (2, 3, 1) and (3, 1, 2). For instance, the following holds for (2, 3, 1):

\lvert A_1 - 1\rvert = 1 \geq K
\lvert A_2 - 2\rvert = 1 \geq K
\lvert A_3 - 3\rvert = 2 \geq K

Sample Input 2

8 3

Sample Output 2

4 5 6 7 8 1 2 3

Sample Input 3

8 6

Sample Output 3

-1

D - AND OR Equation

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

正整数 N, K が与えられます．整数列 \bigl(f(0), f(1), \ldots, f(2^N-1)\bigr) であって，以下の条件をすべて満たすものの個数を 998244353 で割った余りを答えてください．

任意の非負整数 x (0\leq x \leq 2^N-1) に対して 0\leq f(x)\leq K.
任意の非負整数 x, y (0\leq x, y \leq 2^N-1) に対して f(x) + f(y) = f(x \,\mathrm{AND}\, y) + f(x \,\mathrm{OR}\, y).

ただし，\mathrm{AND}, \mathrm{OR} はそれぞれビットごとの論理積，論理和を表します．

制約

1\leq N\leq 3\times 10^5
1\leq K\leq 10^{18}

入力

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

N K

出力

条件を満たす整数列の個数を 998244353 で割った余りを出力してください．

入力例 1

2 1

出力例 1

条件を満たす整数列は以下の 6 個です．

(0,0,0,0)
(0,1,0,1)
(0,0,1,1)
(1,0,1,0)
(1,1,0,0)
(1,1,1,1)

入力例 2

2 2

出力例 2

入力例 3

100 123456789123456789

出力例 3

34663745

Score : 700 points

Problem Statement

You are given positive integers N and K. Find the number, modulo 998244353, of integer sequences \bigl(f(0), f(1), \ldots, f(2^N-1)\bigr) that satisfy all of the following conditions:

0\leq f(x)\leq K for all non-negative integers x (0\leq x \leq 2^N-1).
f(x) + f(y) = f(x \,\mathrm{AND}\, y) + f(x \,\mathrm{OR}\, y) for all non-negative integers x and y (0\leq x, y \leq 2^N-1)

Here, \mathrm{AND} and \mathrm{OR} denote the bitwise AND and OR, respectively.

Constraints

1\leq N\leq 3\times 10^5
1\leq K\leq 10^{18}

Input

Input is given from Standard Input in the following format:

N K

Output

Print the number, modulo 998244353, of integer sequences that satisfy the conditions.

Sample Input 1

2 1

Sample Output 1

The following six integer sequences satisfy the conditions:

(0,0,0,0)
(0,1,0,1)
(0,0,1,1)
(1,0,1,0)
(1,1,0,0)
(1,1,1,1)

Sample Input 2

2 2

Sample Output 2

Sample Input 3

100 123456789123456789

Sample Output 3

34663745

E - GCD of Path Weights

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

N 頂点 M 辺からなる有向グラフ G が与えられます．頂点には 1, 2, \ldots, N の番号がついています．i 番目の辺は a_i から b_i に向かう有向辺で，a_i < b_i が成り立っています．

正整数列 W = (W_1, W_2, \ldots, W_N) の美しさを，次が成り立つような正整数 x の最大値として定義します．

G における頂点 1 から頂点 N への任意のパス (v_1, \ldots, v_k) (v_1 = 1, v_k = N) に対し，\sum_{i=1}^k W_{v_i} は x の倍数である．

整数列 A = (A_1, A_2, \ldots, A_N) が与えられます．正整数列 W = (W_1, \ldots, W_N) を，A_i \neq -1 \implies W_i = A_i を満たすように定めるとき，その美しさとしてありうる最大値を求めてください．ただし，最大値が存在しない場合には -1 を出力してください．

制約

2\leq N\leq 3\times 10^5
1\leq M\leq 3\times 10^5
1\leq a_i < b_i \leq N
i\neq j ならば (a_i,b_i)\neq (a_j,b_j)
与えられるグラフ G において，頂点 1 から頂点 N へのパスが存在する．
A_i = -1 または 1\leq A_i\leq 10^{12}

入力

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

N M
a_1 b_1
\vdots
a_M b_M
A_1 A_2 \ldots A_N

出力

正整数列 W の美しさとしてありうる最大値を出力してください．ただし，最大値が存在しない場合には -1 を出力してください．

入力例 1

出力例 1

頂点 1 から頂点 N へのパスは，(1,2,4), (1,3,4) の 2 個です．例えば W = (5, 3, 7, 8) の美しさは 4 となります．実際，W_1 + W_2 + W_4 = 16, W_1 + W_3 + W_4 = 20 はともに 4 の倍数です．

入力例 2

出力例 2

頂点 1 から頂点 N へのパスは，(1,2,4), (1,3,4), (1,4) の 3 個です．例えば W = (5, 3, 7, 8) の美しさは 1 となります．

入力例 3

出力例 3

-1

例えば W = (3, 10^{100}, 10^{100}, 7) の美しさは 10^{100}+10 となります．W の美しさをいくらでも大きくできるため，その最大値は存在しません．

入力例 4

5 5
1 3
3 5
2 3
3 4
1 4
2 -1 3 -1 4

出力例 4

Score : 800 points

Problem Statement

You are given a directed graph G with N vertices and M edges. The vertices are numbered 1, 2, \ldots, N. The i-th edge is directed from Vertex a_i to Vertex b_i, where a_i < b_i.

The beautifulness of a sequence of positive integers W = (W_1, W_2, \ldots, W_N) is defined as the maximum positive integer x that satisfies the following:

For every path (v_1, \ldots, v_k) (v_1 = 1, v_k = N) from Vertex 1 to Vertex N in G, \sum_{i=1}^k W_{v_i} is a multiple of x.

You are given an integer sequence A = (A_1, A_2, \ldots, A_N). Find the maximum beautifulness of a sequence of positive integers W = (W_1, \ldots, W_N) such that A_i \neq -1 \implies W_i = A_i. If the maximum beautifulness does not exist, print -1.

Constraints

2\leq N\leq 3\times 10^5
1\leq M\leq 3\times 10^5
1\leq a_i < b_i \leq N
(a_i,b_i)\neq (a_j,b_j) if i\neq j
In the given graph G, there is a path from Vertex 1 to Vertex N.
A_i = -1 or 1\leq A_i\leq 10^{12}

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
\vdots
a_M b_M
A_1 A_2 \ldots A_N

Output

Print the maximum beautifulness of a sequence of positive integers W. If the maximum beautifulness does not exist, print -1.

Sample Input 1

Sample Output 1

There are two paths from Vertex 1 to Vertex N: (1,2,4) and (1,3,4). For instance, W = (5, 3, 7, 8) has a beautifulness of 4. Indeed, both W_1 + W_2 + W_4 = 16 and W_1 + W_3 + W_4 = 20 are multiples of 4.

Sample Input 2

Sample Output 2

There are three paths from Vertex 1 to Vertex N: (1,2,4), (1,3,4), and (1,4). For instance, W = (5, 3, 7, 8) has a beautifulness of 1.

Sample Input 3

Sample Output 3

-1

For instance, W = (3, 10^{100}, 10^{100}, 7) has a beautifulness of 10^{100}+10. Since you can increase the beautifulness of W as much as you want, there is no maximum beautifulness.

Sample Input 4

5 5
1 3
3 5
2 3
3 4
1 4
2 -1 3 -1 4

Sample Output 4

F - Arithmetic Sequence Nim

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

正整数 m, 非負整数 a (0\leq a < m) および正整数列 A = (A_1, \ldots, A_N) が与えられます．

正整数からなる集合 X を X = \{x>0\mid x\equiv a \pmod{m}\} により定めます．

先手太郎君と後手次郎君が対戦ゲームをします．ゲームでは先手太郎君の手番から始めて，交互に以下の操作を行います．

添字 i (1\leq i\leq N) と正整数 x\in X の組 (i,x) であって，x\leq A_i を満たすものをひとつ選ぶ．A_i を A_i - x に変更する．ただしそのような (i, x) が存在しないならば，手番のプレイヤーの負けとしてゲームを終了する．

先手太郎君が最初の手番に選ぶことができる (i, x) のうち，それ以降の手番で両者が最善を尽くした場合に先手太郎君が勝つことができるものの個数を 998244353 で割った余りを答えてください．

制約

1\leq N\leq 3\times 10^5
0\leq a < m\leq 10^9
\max(1, a) \leq A_i\leq 10^{18}

入力

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

N m a
A_1 A_2 \ldots A_N

出力

先手太郎君が最初の手番に選ぶことができる (i, x) のうち，それ以降の手番で両者が最善を尽くした場合に先手太郎君が勝つことができるものの個数を 998244353 で割った余りを出力してください．

入力例 1

3 1 0
5 6 7

出力例 1

X = \{1, 2, 3, 4, 5, \ldots\} です．条件を満たす (i,x) は (1,4), (2,4), (3,4) の 3 個です．

入力例 2

5 10 3
5 9 18 23 27

出力例 2

X = \{3, 13, 23, 33, 43, \ldots\} です．条件を満たす (i,x) は (4,23), (5,3), (5,13) の 3 個です．

入力例 3

4 10 8
100 101 102 103

出力例 3

先手太郎君は最善を尽くしても勝つことはできません．したがって条件を満たす (i, x) は 0 個です．

入力例 4

5 2 1
111111111111111 222222222222222 333333333333333 444444444444444 555555555555555

出力例 4

943937640

条件を満たす (i, x) は 833333333333334 個あります． 998244353 で割った余りを出力してください．

Score : 900 points

Problem Statement

You are given a positive integer m, a non-negative integer a (0\leq a < m), and a sequence of positive integers A = (A_1, \ldots, A_N).

A set X of positive integers is defined as X = \{x>0\mid x\equiv a \pmod{m}\}.

Alice and Bob will play a game against each other. They will alternate turns performing the following operation, with Alice going first:

Choose a pair (i,x) of an index i (1\leq i\leq N) and a positite integer x\in X such that x\leq A_i. Change A_i to A_i - x. If there is no such (i, x), the current player loses and the game ends.

Find the number, modulo 998244353, of pairs (i, x) that Alice can choose in her first turn so that she wins if both players play optimally in subsequent turns.

Constraints

1\leq N\leq 3\times 10^5
0\leq a < m\leq 10^9
\max(1, a) \leq A_i\leq 10^{18}

Input

Input is given from Standard Input in the following format:

N m a
A_1 A_2 \ldots A_N

Output

Print the number, modulo 998244353, of pairs (i, x) that Alice can choose in her first turn so that she wins if both players play optimally in subsequent turns.

Sample Input 1

3 1 0
5 6 7

Sample Output 1

We have X = \{1, 2, 3, 4, 5, \ldots\}. Three pairs (i,x) satisfy the condition: (1,4), (2,4), (3,4).

Sample Input 2

5 10 3
5 9 18 23 27

Sample Output 2

We have X = \{3, 13, 23, 33, 43, \ldots\}. Three pairs (i,x) satisfy the condition: (4,23), (5,3), (5,13).

Sample Input 3

4 10 8
100 101 102 103

Sample Output 3

Alice cannot win even if she plays optimally. Thus, zero pairs (i,x) satisfy the condition.

Sample Input 4

5 2 1
111111111111111 222222222222222 333333333333333 444444444444444 555555555555555

Sample Output 4

943937640

833333333333334 pairs (i,x) satisfy the condition. Print the count modulo 998244353.