E - Product

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 個の袋があります。
袋 i には L_i 個のボールが入っていて、袋 i の j(1\leq j\leq L_i) 番目のボールには正の整数 a_{i,j} が書かれています。

それぞれの袋から 1 つずつボールを取り出します。
取り出したボールに書かれた数の総積が X になるような取り出し方は何通りありますか?

ただし、書かれた数が同じであっても全てのボールは区別します。

制約

  • N \geq 2
  • L_i \geq 2
  • 袋に入っているボールの個数の総積は 10^5 を超えない。すなわち、\displaystyle\prod_{i=1}^{N}L_i \leq 10^5
  • 1 \leq a_{i,j} \leq 10^9
  • 1 \leq X \leq 10^{18}
  • 入力に含まれる値は全て整数である。

入力

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

N X
L_1 a_{1,1} a_{1,2} \ldots a_{1,L_1}
L_2 a_{2,1} a_{2,2} \ldots a_{2,L_2}
\vdots
L_N a_{N,1} a_{N,2} \ldots a_{N,L_N}

出力

答えを出力せよ。


入力例 1

2 40
3 1 8 4
2 10 5

出力例 1

2

袋 1 の 3 番目のボールと袋 2 の 1 番目のボールを選ぶと、a_{1,3} \times a_{2,1} = 4 \times 10 = 40 となります。
袋 1 の 2 番目のボールと袋 2 の 2 番目のボールを選ぶと、a_{1,2} \times a_{2,2} = 8 \times 5 = 40 となります。
これ以外に総積が 40 になる取り出し方は存在しないので、答えは 2 です。


入力例 2

3 200
3 10 10 10
3 10 10 10
5 2 2 2 2 2

出力例 2

45

書かれた数が同じであっても全てのボールは区別することに注意してください。


入力例 3

3 1000000000000000000
2 1000000000 1000000000
2 1000000000 1000000000
2 1000000000 1000000000

出力例 3

0

総積が X になる取り出し方が 1 つも存在しないこともあります。

Score : 300 points

Problem Statement

We have N bags.
Bag i contains L_i balls. The j-th ball (1\leq j\leq L_i) in Bag i has a positive integer a_{i,j} written on it.

We will pick out one ball from each bag.
How many ways are there to pick the balls so that the product of the numbers written on the picked balls is X?

Here, we distinguish all balls, even with the same numbers written on them.

Constraints

  • N \geq 2
  • L_i \geq 2
  • The product of the numbers of balls in the bags is at most 10^5: \displaystyle\prod_{i=1}^{N}L_i \leq 10^5.
  • 1 \leq a_{i,j} \leq 10^9
  • 1 \leq X \leq 10^{18}
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X
L_1 a_{1,1} a_{1,2} \ldots a_{1,L_1}
L_2 a_{2,1} a_{2,2} \ldots a_{2,L_2}
\vdots
L_N a_{N,1} a_{N,2} \ldots a_{N,L_N}

Output

Print the answer.


Sample Input 1

2 40
3 1 8 4
2 10 5

Sample Output 1

2

When choosing the 3-rd ball in Bag 1 and 1-st ball in Bag 2, we have a_{1,3} \times a_{2,1} = 4 \times 10 = 40.
When choosing the 2-nd ball in Bag 1 and 2-nd ball in Bag 2, we have a_{1,2} \times a_{2,2} = 8 \times 5 = 40.
There are no other ways to make the product 40, so the answer is 2.


Sample Input 2

3 200
3 10 10 10
3 10 10 10
5 2 2 2 2 2

Sample Output 2

45

Note that we distinguish all balls, even with the same numbers written on them.


Sample Input 3

3 1000000000000000000
2 1000000000 1000000000
2 1000000000 1000000000
2 1000000000 1000000000

Sample Output 3

0

There may be no way to make the product X.

F - kasaka

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

英小文字からなる文字列 S が与えられます。 S の先頭に a をいくつか( 0 個でも良い)つけ加えて回文にすることができるか判定してください。

ただし、長さ N の文字列 A=A_1A_2\ldots A_N が回文であるとは、すべての 1\leq i\leq N について A_i=A_{N+1-i} が成り立っていることをいいます。

制約

  • 1 \leq \lvert S \rvert \leq 10^6
  • S は英小文字のみからなる。

入力

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

S

出力

S の先頭に a をいくつかつけ加えて回文にすることができるならば Yes を、そうでないならば No を出力せよ。


入力例 1

kasaka

出力例 1

Yes

kasaka の先頭に a を 1 つ付け加えることによって、akasaka となり回文となるため Yes を出力します。


入力例 2

atcoder

出力例 2

No

atcoder の先頭に a をいくつ付け加えても回文となる事はありません。


入力例 3

php

出力例 3

Yes

php はそれ自体回文です。S の先頭に付け加える a は 0 個でも許されるため、Yes を出力します。

Score : 300 points

Problem Statement

Given is a string S consisting of lowercase English letters. Determine whether adding some number of a's (possibly zero) at the beginning of S can make it a palindrome.

Here, a string of length N, A=A_1A_2\ldots A_N, is said to be a palindrome when A_i=A_{N+1-i} for every 1\leq i\leq N.

Constraints

  • 1 \leq \lvert S \rvert \leq 10^6
  • S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S

Output

If adding some number of a's (possibly zero) at the beginning of S can make it a palindrome, print Yes; otherwise, print No.


Sample Input 1

kasaka

Sample Output 1

Yes

By adding one a at the beginning of kasaka, we have akasaka, which is a palindrome, so Yes should be printed.


Sample Input 2

atcoder

Sample Output 2

No

Adding any number of a's at the beginning of atcoder does not make it a palindrome.


Sample Input 3

php

Sample Output 3

Yes

php itself is a palindrome. Adding zero a's at the beginning of S is allowed, so Yes should be printed.

G - Magical Cookies

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

H \times W 枚のクッキーが H 行 W 列に並んでいます。
上から i 行目・左から j 列目のクッキーの色は英小文字 c_{i,j} で表されます。

これから、以下の手続きを行います。

1. 各行に対して次の操作を行う : その行に 2 枚以上のクッキーが残っており、それらの色がすべて同じならば、それらに印をつける。

2. 各列に対して次の操作を行う : その列に 2 枚以上のクッキーが残っており、それらの色がすべて同じならば、それらに印をつける。

3. 印のついたクッキーがあればそれらをすべて取り除いて 1. に戻り、なければ手続きを終了する。

手続きを終了した時点で残っているクッキーの枚数を求めてください。

制約

  • 2 \leq H, W \leq 2000
  • c_{i,j} は英小文字である

入力

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

H W
c_{1,1}c_{1,2} \ldots c_{1,W}
c_{2,1}c_{2,2} \ldots c_{2,W}
\vdots
c_{H,1}c_{H,2} \ldots c_{H,W}

出力

答えを出力せよ。


入力例 1

4 3
aaa
aaa
abc
abd

出力例 1

2

以下で示す順で手続きを行います。

  • 1. により、1, 2 行目のクッキーに印をつける。
  • 2. により、1 列目のクッキーに印をつける。
  • 3. により、印を付けたクッキーを取り除く。

この時点でクッキーは以下のようになっています。ただし、クッキーを取り除いた箇所は . で表しています。

...
...
.bc
.bd
  • 1. により、何もしない。
  • 2. により、2 列目のクッキーに印をつける。
  • 3. により、印を付けたクッキーを取り除く。

この時点でクッキーは以下のようになっています。ただし、クッキーを取り除いた箇所は . で表しています。

...
...
..c
..d
  • 1. により、何もしない。
  • 2. により、何もしない。
  • 3. により、印がついているクッキーが存在しないので手続きを終了する。

最終的に残っているクッキーの枚数は 2 枚です。


入力例 2

2 5
aaaaa
abcde

出力例 2

4

入力例 3

3 3
ooo
ooo
ooo

出力例 3

0

Score : 400 points

Problem Statement

There are H \times W cookies in H rows and W columns.
The color of the cookie at the i-row from the top and j-th column from the left is represented by a lowercase English letter c_{i,j}.

We will perform the following procedure.

1. For each row, perform the following operation: if there are two or more cookies remaining in the row and they all have the same color, mark them.

2. For each column, perform the following operation: if there are two or more cookies remaining in the column and they all have the same color, mark them.

3. If there are any marked cookies, remove them all and return to 1; otherwise, terminate the procedure.

Find the number of cookies remaining at the end of the procedure.

Constraints

  • 2 \leq H, W \leq 2000
  • c_{i,j} is a lowercase English letter.

Input

The input is given from Standard Input in the following format:

H W
c_{1,1}c_{1,2} \ldots c_{1,W}
c_{2,1}c_{2,2} \ldots c_{2,W}
\vdots
c_{H,1}c_{H,2} \ldots c_{H,W}

Output

Print the answer.


Sample Input 1

4 3
aaa
aaa
abc
abd

Sample Output 1

2

The procedure is performed as follows.

  • 1. Mark the cookies in the first and second rows.
  • 2. Mark the cookies in the first column.
  • 3. Remove the marked cookies.

At this point, the cookies look like the following, where . indicates a position where the cookie has been removed.

...
...
.bc
.bd
  • 1. Do nothing.
  • 2. Mark the cookies in the second column.
  • 3. Remove the marked cookies.

At this point, the cookies look like the following, where . indicates a position where the cookie has been removed.

...
...
..c
..d
  • 1. Do nothing.
  • 2. Do nothing.
  • 3. No cookies are marked, so terminate the procedure.

The final number of cookies remaining is 2.


Sample Input 2

2 5
aaaaa
abcde

Sample Output 2

4

Sample Input 3

3 3
ooo
ooo
ooo

Sample Output 3

0
H - Hierarchical Majority Vote

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

長さ 3^n \; (n \geq 1) の 01 列 B=B_1 B_2 \dots B_{3^n} に対して、長さ 3^{n-1} の 01 列 C=C_1 C_2 \dots C_{3^{n-1}} を得る操作を以下のように定めます。

  • B の要素を 3 つずつまとめて多数決を取る。すなわち、i=1,2,\dots,3^{n-1} について、B_{3i-2},B_{3i-1},B_{3i} のうち最も多く現れる値を C_i とする。

長さ 3^N の 01 列 A = A_1 A_2 \dots A_{3^N} が与えられます。A に上の操作を N 回適用して得られる長さ 1 の列を A' = A'_1 とします。

A の要素のいくつかを 0 から 1 または 1 から 0 へ変えることを考えたとき、A の要素を最小で何個変えれば、A'_1 の値が変わるか求めてください。

制約

  • N は 1 以上 13 以下の整数
  • A は 0,1 からなる長さ 3^N の文字列

入力

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

N
A_1 A_2 \dots A_{3^N}

出力

答えを出力せよ。


入力例 1

2
010011101

出力例 1

1

A=010011101 に操作を 2 回適用すると、以下のようになります。

  • 1 回目: 010 の過半数は 0, 011 の過半数は 1, 101 の過半数は 1 なので、これらをつなげて 011 を得る。
  • 2 回目: 011 の過半数は 1 なので、 1 を得る。

最終的な値を 1 から 0 にするためには、例えば A の 5 文字目を 1 から 0 にして A=010001101 にすればよいです。変更後、操作は以下のようになります。

  • 1 回目: 010 の過半数は 0, 001 の過半数は 0, 101 の過半数は 1 なので、これらをつなげて 001 を得る。
  • 2 回目: 001 の過半数は 0 なので、 0 を得る。

よって、 A の要素を 1 個変えるのが最小です。


入力例 2

1
000

出力例 2

2

Score : 450 points

Problem Statement

For a binary string B = B_1 B_2 \dots B_{3^n} of length 3^n (n \geq 1), we define an operation to obtain a binary string C = C_1 C_2 \dots C_{3^{n-1}} of length 3^{n-1} as follows:

  • Partition the elements of B into groups of 3 and take the majority value from each group. That is, for i=1,2,\dots,3^{n-1}, let C_i be the value that appears most frequently among B_{3i-2}, B_{3i-1}, and B_{3i}.

You are given a binary string A = A_1 A_2 \dots A_{3^N} of length 3^N. Let A' = A'_1 be the length-1 string obtained by applying the above operation N times to A.

Determine the minimum number of elements of A that must be changed (from 0 to 1 or from 1 to 0) in order to change the value of A'_1.

Constraints

  • N is an integer with 1 \leq N \leq 13.
  • A is a string of length 3^N consisting of 0 and 1.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_{3^N}

Output

Print the answer.


Sample Input 1

2
010011101

Sample Output 1

1

For example, with A=010011101, after applying the operation twice, we obtain:

  • First operation: The majority of 010 is 0, of 011 is 1, and of 101 is 1, resulting in 011.
  • Second operation: The majority of 011 is 1, yielding 1.

To change the final value from 1 to 0, one way is to change the 5th character of A from 1 to 0, yielding A=010001101. After the change, the operations yield:

  • First operation: The majority of 010 is 0, of 001 is 0, and of 101 is 1, resulting in 001.
  • Second operation: The majority of 001 is 0, yielding 0.

Thus, the minimum number of changes required is 1.


Sample Input 2

1
000

Sample Output 2

2
I - Hop Sugoroku

Time Limit: 2.5 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

一列に並んだ N 個のマス 1,2,\dots,N と長さ N の数列 A=(A_1,A_2,\dots,A_N) があります。
最初、マス 1 は黒く、他の N-1 個のマスは白く塗られており、 1 つのコマがマス 1 に置かれています。

以下の操作を 0 回以上好きな回数繰り返します。

  • コマがマス i にあるとき、ある正整数 x を決めてコマをマス i + A_i \times x に移動させる。
    • 但し、 i + A_i \times x > N となるような移動はできません。
  • その後、マス i + A_i \times x を黒く塗る。

操作を終えた時点で黒く塗られたマスの集合として考えられるものの数を 998244353 で割った余りを求めてください。

制約

  • 入力は全て整数
  • 1 \le N \le 2 \times 10^5
  • 1 \le A_i \le 2 \times 10^5

入力

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

N
A_1 A_2 \dots A_N

出力

答えを整数として出力せよ。


入力例 1

5
1 2 3 1 1

出力例 1

8

黒く塗られたマスの集合として考えられるものは以下の 8 通りです。

  • マス 1
  • マス 1,2
  • マス 1,2,4
  • マス 1,2,4,5
  • マス 1,3
  • マス 1,4
  • マス 1,4,5
  • マス 1,5

入力例 2

1
200000

出力例 2

1

入力例 3

40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

出力例 3

721419738

998244353 で割った余りを求めることに注意してください。

Score : 525 points

Problem Statement

There is a row of N squares labeled 1,2,\dots,N and a sequence A=(A_1,A_2,\dots,A_N) of length N.
Initially, square 1 is painted black, the other N-1 squares are painted white, and a piece is placed on square 1.

You may repeat the following operation any number of times, possibly zero:

  • When the piece is on square i, choose a positive integer x and move the piece to square i + A_i \times x.
    • Here, you cannot make a move with i + A_i \times x > N.
  • Then, paint the square i + A_i \times x black.

Find the number of possible sets of squares that can be painted black at the end of the operations, modulo 998244353.

Constraints

  • All input values are integers.
  • 1 \le N \le 2 \times 10^5
  • 1 \le A_i \le 2 \times 10^5

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the answer as an integer.


Sample Input 1

5
1 2 3 1 1

Sample Output 1

8

There are eight possible sets of squares painted black:

  • Square 1
  • Squares 1,2
  • Squares 1,2,4
  • Squares 1,2,4,5
  • Squares 1,3
  • Squares 1,4
  • Squares 1,4,5
  • Squares 1,5

Sample Input 2

1
200000

Sample Output 2

1

Sample Input 3

40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 3

721419738

Be sure to find the number modulo 998244353.