AtCoder Daily Training ALL 2026/03/17 16:00start

Please sign in first.

A - Count Down

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N 以下の非負整数を大きい方から順にすべて出力してください。

制約

1 \leq N \leq 100
N は整数

入力

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

出力

N 以下の非負整数が X 個存在するとき、X 行出力せよ。
i=1,2,\ldots,X に対し、i 行目には N 以下の非負整数のうち大きい方から i 番目のものを出力せよ。

入力例 1

出力例 1

3 以下の非負整数は 0,1,2,3 の 4 個です。
1 行目に 3 を、2 行目に 2 を、3 行目に 1 を、4 行目に 0 を出力することでこれらを大きい方から順に出力したことになります。

入力例 2

出力例 2

Score : 100 points

Problem Statement

Print all non-negative integers less than or equal to N in descending order.

Constraints

1 \leq N \leq 100
N is an integer.

Input

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

Output

Print X lines, where X is the number of non-negative integers less than or equal to N.
For each i=1, 2, \ldots, X, the i-th line should contain the i-th greatest non-negative integer less than or equal to N.

Sample Input 1

Sample Output 1

We have four non-negative integers less than or equal to 3, which are 0, 1, 2, and 3.
To print them in descending order, print 3 in the first line, 2 in the second, 1 in the third, and 0 in the fourth.

Sample Input 2

Sample Output 2

B - Humidifier 1

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

AtCoder社のオフィスには加湿器が 1 つあります。現在は時刻 0 であり、加湿器には水が入っていません。

あなたはこの加湿器にこれから N 回水を追加します。i 回目 (1\leq i \leq N)の水の追加は時刻 T_i に行い、水を V_i リットル追加します。なお、 T_i < T_{i+1} (1 \leq i \leq N-1) を満たすことが保証されます。

ただし、加湿器には穴が空いていて、加湿器に水が入っている間は 1 単位時間につき水が 1 リットル減り続けます。

時刻 T_N に水を追加し終えたとき、加湿器に残っている水の量を求めてください。

制約

1 \leq N \leq 100
1 \leq T_i \leq 100 (1 \leq i \leq N)
1 \leq V_i \leq 100 (1 \leq i \leq N)
T_i < T_{i+1} (1 \leq i \leq N-1)
入力は全て整数

入力

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

N
T_1 V_1
T_2 V_2
\vdots
T_N V_N

出力

答えを出力せよ。

入力例 1

出力例 1

時系列で以下のように水が追加されます。

時刻 1 : 水を追加する前は 0 リットル入っており、3 リットル追加して加湿器には 3 リットルの水が入っています。
時刻 3 : 水を追加する前は 1 リットル入っており、1 リットル追加して加湿器には 2 リットルの水が入っています。
時刻 4 : 水を追加する前は 1 リットル入っており、4 リットル追加して加湿器には 5 リットルの水が入っています。
時刻 7 : 水を追加する前は 2 リットル入っており、1 リットル追加して加湿器には 3 リットルの水が入っています。

時刻 7 に水を追加し終えたとき、加湿器に残っている水の量は 3 リットルです。よって答えは 3 です。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 150 points

Problem Statement

There is one humidifier in the AtCoder company office. The current time is 0, and the humidifier has no water inside.

You will add water to this humidifier N times. The i-th addition of water (1 \leq i \leq N) takes place at time T_i, and you add V_i liters of water. It is guaranteed that T_i < T_{i+1} for all 1 \leq i \leq N-1.

However, the humidifier has a leak, and as long as there is water inside, the amount of water decreases by 1 liter per unit time.

Find the amount of water remaining in the humidifier immediately after you finish adding water at time T_N.

Constraints

1 \leq N \leq 100
1 \leq T_i \leq 100 (1 \leq i \leq N)
1 \leq V_i \leq 100 (1 \leq i \leq N)
T_i < T_{i+1} (1 \leq i \leq N-1)
All input values are integers.

Input

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

N
T_1 V_1
T_2 V_2
\vdots
T_N V_N

Output

Print the answer.

Sample Input 1

Sample Output 1

At each point in time, water is added as follows:

Time 1: Before adding, the humidifier has 0 liters. After adding 3 liters, it has 3 liters.
Time 3: Before adding, it has 1 liter. After adding 1 liter, it has 2 liters total.
Time 4: Before adding, it has 1 liter. After adding 4 liters, it has 5 liters total.
Time 7: Before adding, it has 2 liters. After adding 1 liter, it has 3 liters total.

After finishing the addition at time 7, the humidifier contains 3 liters. Thus, the answer is 3.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

C - AtCoder Amusement Park

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

AtCoder 遊園地には K 人乗りのアトラクションがあります。現在、このアトラクションの待機列には N グループが並んでいます。

先頭から i 番目 (1\leq i\leq N) のグループは A _ i 人組です。すべての i (1\leq i\leq N) について、A _ i\leq K です。

高橋君はこのアトラクションのスタッフとして、並んでいるグループを次の手順に従って誘導します。

はじめ、アトラクションには誰も誘導されておらず、空席は K 個あります。

待機列に並んでいるグループがない場合、アトラクションをスタートさせ、誘導を終了する。
アトラクションの空席の数と待機列の先頭に並んでいるグループの人数を比較し、次のどちらかを行う。
- 待機列の先頭に並んでいるグループの人数よりアトラクションの空席の数のほうが少ない場合、アトラクションをスタートさせる。スタートしたのち、アトラクションの空席が K 個になる。
- そうでない場合、待機列の先頭に並んでいるグループを全員アトラクションへ誘導する。先頭のグループが待機列から取り出され、アトラクションの空席がグループの人数ぶんだけ減少する。
1 に戻る。

ただし、誘導を開始したあとに追加でグループが並ぶことはないとします。以上の条件のもとで、この手順が有限回で終了することが示せます。

高橋君が誘導を開始してから誘導を終了するまで、何回アトラクションをスタートさせるか求めてください。

制約

1\leq N\leq100
1\leq K\leq100
1\leq A _ i\leq K\ (1\leq i\leq N)
入力はすべて整数

入力

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

N K
A _ 1 A _ 2 \ldots A _ N

出力

答えを出力せよ。

入力例 1

7 6
2 5 1 4 1 2 3

出力例 1

はじめ、7 つのグループは以下のように並んでいます。

高橋君の誘導の様子の一部を以下の図に示します。

はじめ、先頭に並んでいるグループは 2 人のグループで、空席は 6 個です。よって、高橋君は先頭のグループをアトラクションに誘導し、空席は 4 個になります。
次に、先頭に並んでいるグループは 5 人のグループで、空席の個数 4 より多いため、アトラクションをスタートさせます。
空席が 6 個になったため、先頭のグループをアトラクションに誘導し、空席は 1 個になります。
次に先頭に並んでいるのは 1 人なので、アトラクションに誘導し、空席は 0 個になります。

すべての誘導が終了するまでに、高橋君は 4 回アトラクションをスタートさせることになります。よって、4 を出力してください。

入力例 2

7 10
1 10 1 10 1 10 1

出力例 2

入力例 3

15 100
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60

出力例 3

Score: 200 points

Problem Statement

The AtCoder amusement park has an attraction that can accommodate K people. Now, there are N groups lined up in the queue for this attraction.

The i-th group from the front (1\leq i\leq N) consists of A_i people. For all i (1\leq i\leq N), it holds that A_i \leq K.

Takahashi, as a staff member of this attraction, will guide the groups in the queue according to the following procedure.

Initially, no one has been guided to the attraction, and there are K empty seats.

If there are no groups in the queue, start the attraction and end the guidance.
Compare the number of empty seats in the attraction with the number of people in the group at the front of the queue, and do one of the following:
- If the number of empty seats is less than the number of people in the group at the front, start the attraction. Then, the number of empty seats becomes K again.
- Otherwise, guide the entire group at the front of the queue to the attraction. The front group is removed from the queue, and the number of empty seats decreases by the number of people in the group.
Go back to step 1.

Here, no additional groups will line up after the guidance has started. Under these conditions, it can be shown that this procedure will end in a finite number of steps.

Determine how many times the attraction will be started throughout the guidance.

Constraints

1\leq N\leq 100
1\leq K\leq 100
1\leq A_i\leq K\ (1\leq i\leq N)
All input values are integers.

Input

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

N K
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

7 6
2 5 1 4 1 2 3

Sample Output 1

Initially, the seven groups are lined up as follows:

Part of Takahashi's guidance is shown in the following figure:

Initially, the group at the front has 2 people, and there are 6 empty seats. Thus, he guides the front group to the attraction, leaving 4 empty seats.
Next, the group at the front has 5 people, which is more than the 4 empty seats, so the attraction is started.
After the attraction is started, there are 6 empty seats again, so the front group is guided to the attraction, leaving 1 empty seat.
Next, the group at the front has 1 person, so they are guided to the attraction, leaving 0 empty seats.

In total, he starts the attraction four times before the guidance is completed. Therefore, print 4.

Sample Input 2

7 10
1 10 1 10 1 10 1

Sample Output 2

Sample Input 3

15 100
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60

Sample Output 3

D - Split?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

ボウリングのピンは 1 から 10 の番号が付けられており、上から見ると下図のように配置されます。

この図の二つの点線に挟まれた部分を列と呼ぶことにします。
例えば、ピン 1, 5 とピン 3, 9 はそれぞれ同じ列に存在します。

いくつかのピンが倒れた状態のうち、特殊なものはスプリットと呼ばれます。
ピンの配置がスプリットであるとは、以下の条件が全て成り立つことを言います。

ピン 1 が倒れている。
ある二つの異なる列であって、次の条件を満たすものが存在する。
- それぞれの列には、立っているピンが 1 本以上存在する。
- それらの列の間に、ピンが全て倒れている列が存在する。

具体例は入出力例を参考にしてください。

さて、あるピンの配置が長さ 10 の文字列 S として与えられます。 i = 1, \dots, 10 について、ピン i が倒れているとき S の i 文字目は 0 であり、ピン i が立っているとき S の i 文字目は 1 です。
S で表されるピンの配置がスプリットかどうか判定してください。

制約

S は 0 と 1 からなる長さ 10 の文字列

入力

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

出力

S で表されるピンの配置がスプリットなら Yes を、そうでないなら No を出力せよ。

入力例 1

0101110101

出力例 1

Yes

倒れているピンを灰色で、立っているピンを白色で示すと下図のようになります。

ex0

ピン 5 が立っている列とピン 6 が立っている列の間にはピン 3, 9 が置かれている列が存在しますが、ピン 3, 9 はいずれも倒れているので、この配置はスプリットです。

入力例 2

0100101001

出力例 2

Yes

ex1

入力例 3

0000100110

出力例 3

No

ex2

この配置はスプリットではありません。

入力例 4

1101110101

出力例 4

No

ex3

ピン 1 が倒れていないので、スプリットではありません。

Score : 200 points

Problem Statement

Bowling pins are numbered 1 through 10. The following figure is a top view of the arrangement of the pins:

Let us call each part between two dotted lines in the figure a column.
For example, Pins 1 and 5 belong to the same column, and so do Pin 3 and 9.

When some of the pins are knocked down, a special situation called split may occur.
A placement of the pins is a split if both of the following conditions are satisfied:

Pin 1 is knocked down.
There are two different columns that satisfy both of the following conditions:
- Each of the columns has one or more standing pins.
- There exists a column between these columns such that all pins in the column are knocked down.

See also Sample Inputs and Outputs for examples.

Now, you are given a placement of the pins as a string S of length 10. For i = 1, \dots, 10, the i-th character of S is 0 if Pin i is knocked down, and is 1 if it is standing.
Determine if the placement of the pins represented by S is a split.

Constraints

S is a string of length 10 consisting of 0 and 1.

Input

Input is given from Standard Input in the following format:

Output

If the placement of the pins represented by S is a split, print Yes; otherwise, print No.

Sample Input 1

0101110101

Sample Output 1

Yes

In the figure below, the knocked-down pins are painted gray, and the standing pins are painted white:

ex0

Between the column containing a standing pin 5 and the column containing a standing pin 6 is a column containing Pins 3 and 9. Since Pins 3 and 9 are both knocked down, the placement is a split.

Sample Input 2

0100101001

Sample Output 2

Yes

ex1

Sample Input 3

0000100110

Sample Output 3

No

ex2

This placement is not a split.

Sample Input 4

1101110101

Sample Output 4

No

ex3

This is not a split because Pin 1 is not knocked down.

E - Cycle Graph?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1,2,\dots,N の番号が、辺には 1,2,\dots,M の番号がつけられており、辺 i は頂点 A_i と頂点 B_i を結んでいます。

このグラフがサイクルグラフであるか判定してください。

単純無向グラフとは

単純無向グラフとは、自己ループや多重辺を含まず、辺に向きの無いグラフのことをいいます。

サイクルグラフとは

頂点に 1, 2, \dots, N の番号が付けられた N 頂点のグラフがサイクルグラフであるとは、(1, 2, \dots, N) を並べ変えて得られる数列 (v_1, v_2, \dots, v_N) であって、以下の条件を満たすものが存在することをいいます。

i = 1, 2, \dots, N-1 に対して、頂点 v_i と v_{i+1} を結ぶ辺が存在する
頂点 v_N と v_1 を結ぶ辺が存在する
それら以外の辺は存在しない

制約

3\leq N \leq 2\times 10^5
0 \leq M \leq 2\times 10^5
1 \leq A_i, B_i \leq N
与えられるグラフは単純
入力は全て整数

入力

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

N M
A_1 B_1
\vdots
A_M B_M

出力

与えられたグラフがサイクルグラフであるなら Yes、そうでないなら No と出力せよ。

入力例 1

出力例 1

Yes

与えられたグラフは以下の通りであり、これはサイクルグラフです。

入力例 2

出力例 2

No

与えられたグラフは以下の通りであり、これはサイクルグラフではありません。

Score : 300 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1,2,\dots,N and the edges are numbered 1,2,\dots,M. Edge i connects vertices A_i and B_i.

Determine whether this graph is a cycle graph.

Definition of simple undirected graph

A simple undirected graph is a graph with undirected edges without self-loops or multi-edges.

Definition of cycle graph

An N-vertex graph with vertices labeled 1,2,\dots,N is a cycle graph when there exists a permutation (v_1,v_2,\dots,v_N) of (1,2,\dots,N) such that:

For each i = 1,2,\dots,N-1, there is an edge between vertices v_i and v_{i+1}.
There is an edge between vertices v_N and v_1.
No other edges exist.

Constraints

3 \le N \le 2\times 10^5
0 \le M \le 2\times 10^5
1 \le A_i, B_i \le N
The given graph is simple.
All input values are integers.

Input

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

N M
A_1 B_1
\vdots
A_M B_M

Output

Output Yes if the given graph is a cycle graph; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

The given graph is as follows, and this is a cycle graph.

Sample Input 2

Sample Output 2

No

The given graph is as follows, and this is not a cycle graph.

F - ABC conjecture

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

正の整数 N が与えられます。

A\leq B\leq C かつ ABC\leq N であるような正の整数の組 (A,B,C) の個数を求めてください。

なお、制約の条件下で答えは 2^{63} 未満であることが保証されます。

制約

1 \leq N \leq 10^{11}
N は整数である

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

条件を満たす組は (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2) の 5 つです。

入力例 2

出力例 2

入力例 3

100000000000

出力例 3

5745290566750

Score : 300 points

Problem Statement

You are given a positive integer N.

Find the number of triples of positive integers (A, B, C) such that A\leq B\leq C and ABC\leq N.

The Constraints guarantee that the answer is less than 2^{63}.

Constraints

1 \leq N \leq 10^{11}
N is an integer.

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

Sample Output 1

There are five such triples: (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2).

Sample Input 2

Sample Output 2

Sample Input 3

100000000000

Sample Output 3

5745290566750

G - Multiply and Rotate

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

正の整数 a があります。また、黒板に 1 個の数が 10 進表記で書かれています。
黒板に現在書かれている数を x としたとき、高橋君は次のいずれかの操作を行い、黒板に書かれている数を変化させることができます。

x を消し、 x を a 倍した数を 10 進表記で新たに書きこむ。
x を文字列とみなして、列の末尾の数字を文字列の先頭に移動させる。
ただし、この操作は x \geq 10 かつ x が 10 で割り切れないときにしか行えない。

たとえば a = 2, x = 123 であるとき、高橋君は次のいずれかの操作を行うことができます。

x を消して、 x \times a = 123 \times 2 = 246 を新たに書きこむ。
x を文字列とみなして、123 の末尾の数字である 3 を先頭に移動させる。黒板に書かれている数は 123 から 312 に変化する。

はじめ、黒板には 1 が書かれています。書かれている数を N に変化させるには最小で何回の操作が必要ですか？ただし、どのように操作しても書かれている数を N に変化させられない場合は -1 を出力してください。

制約

2 \leq a \lt 10^6
2 \leq N \lt 10^6
入力はすべて整数である。

入力

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

a N

出力

答えを出力せよ。

入力例 1

3 72

出力例 1

以下に説明する操作を行うことで、黒板に書かれている数を 4 回で 1 から 72 に変化させることができます。

1 つ目の操作を行う。黒板に書かれている数は 1 \to 3 に変わる。
1 つ目の操作を行う。黒板に書かれている数は 3 \to 9 に変わる。
1 つ目の操作を行う。黒板に書かれている数は 9 \to 27 に変わる。
2 つ目の操作を行う。黒板に書かれている数は 27 \to 72 に変わる。

3 回以下の操作で 72 に変化させることはできないため、答えは 4 になります。

入力例 2

2 5

出力例 2

-1

どのように操作しても黒板に書かれている数を 5 に変化させることはできません。

入力例 3

2 611

出力例 3

適切に操作を選ぶことで、 1 \to 2 \to 4 \to 8 \to 16 \to 32 \to 64 \to 46 \to 92 \to 29 \to 58 \to 116 \to 611 と 12 回の操作で黒板に書かれている数を 611 に変化させることができ、これが最小です。

入力例 4

2 767090

出力例 4

Score : 400 points

Problem Statement

We have a positive integer a. Additionally, there is a blackboard with a number written in base 10.
Let x be the number on the blackboard. Takahashi can do the operations below to change this number.

Erase x and write x multiplied by a, in base 10.
See x as a string and move the rightmost digit to the beginning.
This operation can only be done when x \geq 10 and x is not divisible by 10.

For example, when a = 2, x = 123, Takahashi can do one of the following.

Erase x and write x \times a = 123 \times 2 = 246.
See x as a string and move the rightmost digit 3 of 123 to the beginning, changing the number from 123 to 312.

The number on the blackboard is initially 1. What is the minimum number of operations needed to change the number on the blackboard to N? If there is no way to change the number to N, print -1.

Constraints

2 \leq a \lt 10^6
2 \leq N \lt 10^6
All values in input are integers.

Input

Input is given from Standard Input in the following format:

a N

Output

Print the answer.

Sample Input 1

3 72

Sample Output 1

We can change the number on the blackboard from 1 to 72 in four operations, as follows.

Do the operation of the first type: 1 \to 3.
Do the operation of the first type: 3 \to 9.
Do the operation of the first type: 9 \to 27.
Do the operation of the second type: 27 \to 72.

It is impossible to reach 72 in three or fewer operations, so the answer is 4.

Sample Input 2

2 5

Sample Output 2

-1

It is impossible to change the number on the blackboard to 5.

Sample Input 3

2 611

Sample Output 3

There is a way to change the number on the blackboard to 611 in 12 operations: 1 \to 2 \to 4 \to 8 \to 16 \to 32 \to 64 \to 46 \to 92 \to 29 \to 58 \to 116 \to 611, which is the minimum possible.

Sample Input 4

2 767090

Sample Output 4

H - Cables and Servers

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

1 から N の番号がついた N 台のサーバーと 1 から M の番号がついた M 本のケーブルがあります。
ケーブル i はサーバー A_i とサーバー B_i を双方向に結んでいます。

以下の操作を何回か( 0 回でもよい)行うことで、全てのサーバー同士がケーブルを介して繋がっているようにしてください。

操作：ケーブルを 1 つ選び、その片方の端を別のサーバーに繋ぎ変える

操作の最小回数と、最小回数となる操作列を求めてください。

制約

2 \leq N \leq 2\times 10^5
N-1 \leq M \leq 2\times 10^5
1 \leq A_i,B_i \leq N
入力は全て整数である

入力

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

操作回数の最小値を K とする。K+1 行出力せよ。
1 行目には K を出力せよ。
i+1 行目には i 回目の操作で選ぶケーブルの番号、繋ぎ変える前に繋がっていたサーバーの番号、繋ぎ変えたあと繋がっているサーバーの番号をこの順に空白区切りで出力せよ。

条件を満たす解が複数存在する場合、どれを出力しても正解とみなされる。

入力例 1

出力例 1

1
1 1 3

ケーブル 1 のサーバー 1 に繋がっている側の端をサーバー 3 に繋ぎ変えることで、サーバー同士がケーブルを介して繋がっている状態にすることができます。

このほか、「ケーブル 5 のサーバー 4 に繋がっている側の端をサーバー 1 に繋ぎ変える」という操作や、「ケーブル 2 のサーバー 2 に繋がっている側の端をサーバー 3 に繋ぎ変える」という操作でもサーバー同士がケーブルを介して繋がっている状態にすることができるため、正解とみなされます。

入力例 2

出力例 2

操作をする必要がないこともあります。

入力例 3

出力例 3

Score : 450 points

Problem Statement

There are N servers numbered from 1 to N and M cables numbered from 1 to M.
Cable i connects servers A_i and B_i bidirectionally.

By performing the following operation some number of times (possibly zero), make all servers connected via cables.

Operation: Choose one cable and reconnect one of its ends to a different server.

Find the minimum number of operations required and output an operation sequence achieving this minimum.

Constraints

2 \leq N \leq 2\times 10^5
N-1 \leq M \leq 2\times 10^5
1 \leq A_i, B_i \leq N
All input values are integers.

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 the minimum number of operations be K. Print K+1 lines.

The first line should contain K.
The (i+1)-th line should contain three space-separated integers: the number of the cable chosen in the i-th operation, the server number that was originally connected at that end, and the server number to which it is connected after the operation, in this order.

If there are multiple valid solutions, any one of them will be accepted.

Sample Input 1

Sample Output 1

1
1 1 3

By reconnecting the end of cable 1 that is connected to server 1 to server 3, the servers can be connected via cables.

Operations such as reconnecting the end of cable 5 that is connected to server 4 to server 1, or reconnecting the end of cable 2 that is connected to server 2 to server 3, will also result in all servers being connected and are considered correct.

Sample Input 2

Sample Output 2

No operation may be necessary.

Sample Input 3

Sample Output 3

I - Shift Table

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

高橋君と青木君は、これから N 日間アルバイトをします。
高橋君のシフト表は文字列 S により与えられ、S の i 文字目が # のとき i 日目に出勤、. のとき i 日目に欠勤します。
これをもとに、青木君は以下のようにシフト表を作りました。

まず、N でない N の正の約数 M をとる。
次に、1 日目から M 日目までの勤怠を決める。
最後に、i = 1, 2, \ldots, N - M の順に M + i 日目の勤怠が i 日目の勤怠と一致するように M + i 日目の勤怠を決める。

ここで、M の値が異なる場合でも最終的にできたシフトが同じものとなることがあることに注意してください。

N 日すべてについて高橋君と青木君の少なくとも一方が出勤することになったとき、青木君のシフト表として考えられるものの個数を 998244353 で割った余りを求めてください。

制約

N は 2 以上 10^5 以下の整数
S は長さ N の #、. からなる文字列

入力

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

N
S

出力

答えを出力せよ。

入力例 1

6
##.#.#

出力例 1

高橋君は 1 \cdot 2 \cdot 4 \cdot 6 日目に出勤します。
青木君のシフト表を表す文字列を T とし、青木君は T の i 文字目が # のとき i 日目に出勤、. のとき i 日目に欠勤するとします。
T としてあり得るものは ###### \cdot #.#.#. \cdot .##.## の 3 つです。

1 つめのシフト表は M を 1 または 2 または 3、2 つめのシフト表は M = 2、3 つめのシフト表は M = 3 とすることにより実現できます。

入力例 2

7
...####

出力例 2

入力例 3

12
####.####.##

出力例 3

Score : 525 points

Problem Statement

Takahashi and Aoki will work part-time for the next N days.
Takahashi's shift schedule is given by the string S, where the i-th character of S is # if he works on the i-th day, and . if he is absent on the i-th day.
Based on this, Aoki created his shift schedule as follows.

First, take a positive divisor M of N that is not equal to N.
Next, decide the attendance for the first M days.
Finally, for i = 1, 2, \ldots, N - M in this order, decide the attendance for the (M + i)-th day so that it matches the attendance for the i-th day.

Note that different values of M may lead to the same final shift schedule.

Find the number of possible shift schedules for Aoki such that at least one of Takahashi and Aoki works on each of the N days, modulo 998244353.

Constraints

N is an integer between 2 and 10^5, inclusive.
S is a string of length N consisting of # and ..

Input

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

N
S

Output

Print the answer.

Sample Input 1

6
##.#.#

Sample Output 1

Takahashi works on days 1, 2, 4, and 6.
Let T be the string representing Aoki's shift schedule, where the i-th character of T is # if he works on the i-th day, and . if he is absent on the i-th day.
There are three possible strings for T: ######, #.#.#., and .##.##.

The first shift schedule can be realized by choosing M = 1 or 2 or 3, the second by choosing M = 2, and the third by choosing M = 3.

Sample Input 2

7
...####

Sample Output 2

Sample Input 3

12
####.####.##