A - Takahashi Calendar

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200

問題文

今日は 824 日、年に 5 日しかない積の日です。

d2 桁の整数で、d1 の位を d_110 の位を d_{10} としたときに m, d_1, d_{10} が次の条件をすべて満たす場合、md 日を積の日と呼びます。

  • d_1 \geq 2
  • d_{10} \geq 2
  • d_1 \times d_{10} = m

高橋くんはこの日をもっと増やしたいと考え、1 年が 1 月から M 月までの合計 M ヶ月、どの月も 1 日から D 日までの合計 D 日からなる高橋暦を誕生させました。

高橋暦において、積の日は年に何日あるでしょうか。

制約

  • 入力は全て整数である。
  • 1 \leq M \leq 100
  • 1 \leq D \leq 99

入力

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

M D

出力

高橋暦において積の日が 1 年のうちに訪れる回数を出力せよ。


入力例 1

15 40

出力例 1

10

年に訪れる積の日は次の 10 日です。

  • 422
  • 623
  • 632
  • 824
  • 933
  • 1025
  • 1226
  • 1234
  • 1427
  • 1535

入力例 2

12 31

出力例 2

5

入力例 3

1 1

出力例 3

0

Score : 200 points

Problem Statement

Today is August 24, one of the five Product Days in a year.

A date m-d (m is the month, d is the date) is called a Product Day when d is a two-digit number, and all of the following conditions are satisfied (here d_{10} is the tens digit of the day and d_1 is the ones digit of the day):

  • d_1 \geq 2
  • d_{10} \geq 2
  • d_1 \times d_{10} = m

Takahashi wants more Product Days, and he made a new calendar called Takahashi Calendar where a year consists of M month from Month 1 to Month M, and each month consists of D days from Day 1 to Day D.

In Takahashi Calendar, how many Product Days does a year have?

Constraints

  • All values in input are integers.
  • 1 \leq M \leq 100
  • 1 \leq D \leq 99

Input

Input is given from Standard Input in the following format:

M D

Output

Print the number of Product Days in a year in Takahashi Calender.


Sample Input 1

15 40

Sample Output 1

10

There are 10 Product Days in a year, as follows (m-d denotes Month m, Day d):

  • 4-22
  • 6-23
  • 6-32
  • 8-24
  • 9-33
  • 10-25
  • 12-26
  • 12-34
  • 14-27
  • 15-35

Sample Input 2

12 31

Sample Output 2

5

Sample Input 3

1 1

Sample Output 3

0
B - Kleene Inversion

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300

問題文

長さ N の整数列 A~=~A_0,~A_1,~...,~A_{N - 1} があります。

AK 回繰り返した長さ K \times N の整数列を B とします。たとえば A~=~1,~3,~2K~=~2 のとき、 B~=~1,~3,~2,~1,~3,~2 です。

B の転倒数を 10^9 + 7 で割った余りを求めてください。

ここで B の転倒数は、整数の順序対 (i,~j)~(0 \leq i < j \leq K \times N - 1) であって B_i > B_j を満たすものの個数として定義されます。

制約

  • 入力は全て整数である。
  • 1 \leq N \leq 2000
  • 1 \leq K \leq 10^9
  • 1 \leq A_i \leq 2000

入力

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

N K
A_0 A_1 ... A_{N - 1}

出力

B の転倒数を 10^9 + 7 で割った余りを出力せよ。


入力例 1

2 2
2 1

出力例 1

3

このケースでは B~=~2,~1,~2,~1 です。

  • B_0 > B_1
  • B_0 > B_3
  • B_2 > B_3

であり、B の転倒数は 3 です。


入力例 2

3 5
1 1 1

出力例 2

0

A は同じ数を複数含むこともあります。


入力例 3

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

出力例 3

185297239

10^9 + 7 で割った余りを出力することに注意してください。

Score : 300 points

Problem Statement

We have a sequence of N integers A~=~A_0,~A_1,~...,~A_{N - 1}.

Let B be a sequence of K \times N integers obtained by concatenating K copies of A. For example, if A~=~1,~3,~2 and K~=~2, B~=~1,~3,~2,~1,~3,~2.

Find the inversion number of B, modulo 10^9 + 7.

Here the inversion number of B is defined as the number of ordered pairs of integers (i,~j)~(0 \leq i < j \leq K \times N - 1) such that B_i > B_j.

Constraints

  • All values in input are integers.
  • 1 \leq N \leq 2000
  • 1 \leq K \leq 10^9
  • 1 \leq A_i \leq 2000

Input

Input is given from Standard Input in the following format:

N K
A_0 A_1 ... A_{N - 1}

Output

Print the inversion number of B, modulo 10^9 + 7.


Sample Input 1

2 2
2 1

Sample Output 1

3

In this case, B~=~2,~1,~2,~1. We have:

  • B_0 > B_1
  • B_0 > B_3
  • B_2 > B_3

Thus, the inversion number of B is 3.


Sample Input 2

3 5
1 1 1

Sample Output 2

0

A may contain multiple occurrences of the same number.


Sample Input 3

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

Sample Output 3

185297239

Be sure to print the output modulo 10^9 + 7.

C - Cell Inversion

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500

問題文

2N 個のマスが左右一列に並んでおり、各マスの色を表す長さ 2N の文字列 S が与えられます。

左から i 番目のマスの色は、Si 文字目が B のとき黒色で、W のとき白色です。

あなたは異なる 2 マスを選んで、それらのマスおよびそれらの間にあるマスの色を反転する操作をちょうど N 回行います。 ここで、マスの色を反転するとは、そのマスの色が黒色なら白色に、白色なら黒色にすることです。

ただし、操作を通して同じマスを 2 回以上選ぶことはできません。 つまり、各マスがちょうど 1 回ずつ選ばれることになります。

N 回の操作終了後に全てのマスを白色にする方法が何通りあるかを 10^9+7 で割った余りを求めてください。

ここで、条件を満たす 2 つの方法が異なるとは、1 つ目の方法で i 番目に選んだ 2 つのマスの組と 2 つ目の方法で i 番目に選んだ 2 つのマスの組が異なるような i (1 \leq i \leq N) が存在することをいいます。

制約

  • 1 \leq N \leq 10^5
  • |S| = 2N
  • S の各文字は B または W である。

入力

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

N
S

出力

N 回の操作終了後に全てのマスを白色にする方法の個数を 10^9+7 で割った余りを出力せよ。そのような方法が存在しない場合、代わりに 0 を出力せよ。


入力例 1

2
BWWB

出力例 1

4

全てのマスを白色にする方法は次の 4 通りあります。

  • 最初の操作では 1, 3 番目のマスを選び、次の操作では 2, 4 番目のマスを選びます。
  • 最初の操作では 2, 4 番目のマスを選び、次の操作では 1, 3 番目のマスを選びます。
  • 最初の操作では 1, 4 番目のマスを選び、次の操作では 2, 3 番目のマスを選びます。
  • 最初の操作では 2, 3 番目のマスを選び、次の操作では 1, 4 番目のマスを選びます。

入力例 2

4
BWBBWWWB

出力例 2

288

入力例 3

5
WWWWWWWWWW

出力例 3

0

Score : 500 points

Problem Statement

There are 2N squares arranged from left to right. You are given a string of length 2N representing the color of each of the squares.

The color of the i-th square from the left is black if the i-th character of S is B, and white if that character is W.

You will perform the following operation exactly N times: choose two distinct squares, then invert the colors of these squares and the squares between them. Here, to invert the color of a square is to make it white if it is black, and vice versa.

Throughout this process, you cannot choose the same square twice or more. That is, each square has to be chosen exactly once.

Find the number of ways to make all the squares white at the end of the process, modulo 10^9+7.

Two ways to make the squares white are considered different if and only if there exists i (1 \leq i \leq N) such that the pair of the squares chosen in the i-th operation is different.

Constraints

  • 1 \leq N \leq 10^5
  • |S| = 2N
  • Each character of S is B or W.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the number of ways to make all the squares white at the end of the process, modulo 10^9+7. If there are no such ways, print 0.


Sample Input 1

2
BWWB

Sample Output 1

4

There are four ways to make all the squares white, as follows:

  • Choose Squares 1, 3 in the first operation, and choose Squares 2, 4 in the second operation.
  • Choose Squares 2, 4 in the first operation, and choose Squares 1, 3 in the second operation.
  • Choose Squares 1, 4 in the first operation, and choose Squares 2, 3 in the second operation.
  • Choose Squares 2, 3 in the first operation, and choose Squares 1, 4 in the second operation.

Sample Input 2

4
BWBBWWWB

Sample Output 2

288

Sample Input 3

5
WWWWWWWWWW

Sample Output 3

0
D - Classified

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 600

問題文

AtCoder 本社は N 室の部屋からなる施設であり、部屋には 1 から N の番号がついています。どの 2 部屋の間にも、それらを直接結ぶ通路が 1 本通っています。

社長の高橋君はセキュリティのため、全ての通路に レベル を設定するようあなたに依頼しました。ここで、レベルは正の整数値であり、以下の条件を満たさなければなりません。

  • 全ての部屋 i\ (1 \leq i \leq N) について、部屋 i から出発し、レベルが等しい通路のみをいくつか通って部屋 i に戻るとき、通路を通る回数は必ず偶数になる。

あなたの仕事は、通路ごとのレベルをうまく設定して、レベルの最大値を最小化することです。

制約

  • N2 以上 500 以下の整数

入力

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

N

出力

目的を達成するような設定の仕方を次のように出力してください。

a_{1,2} a_{1,3} ... a_{1,N}
a_{2,3} ... a_{2,N}
.
.
.
a_{N-1,N}

ここで、a_{i,j} は部屋 i と部屋 j の間の通路に設定するレベルです。

答えが複数ありえる場合、どれを出力してもかまいません。


入力例 1

3

出力例 1

1 2
1

この出力例は下の画像のようになります。

たとえば部屋 2 から出発して、2 \to 3 \to 2 \to 3 \to 2 \to 1 \to 2 という経路でレベル 1 の通路のみを通って元の部屋に戻るとき、通路を通る回数は 6 回です。

Score: 600 points

Problem Statement

AtCoder's head office consists of N rooms numbered 1 to N. For any two rooms, there is a direct passage connecting these rooms.

For security reasons, Takahashi the president asked you to set a level for every passage, which is a positive integer and must satisfy the following condition:

  • For each room i\ (1 \leq i \leq N), if we leave Room i, pass through some passages whose levels are all equal and get back to Room i, the number of times we pass through a passage is always even.

Your task is to set levels to the passages so that the highest level of a passage is minimized.

Constraints

  • N is an integer between 2 and 500 (inclusive).

Input

Input is given from Standard Input in the following format:

N

Output

Print one way to set levels to the passages so that the objective is achieved, as follows:

a_{1,2} a_{1,3} ... a_{1,N}
a_{2,3} ... a_{2,N}
.
.
.
a_{N-1,N}

Here a_{i,j} is the level of the passage connecting Room i and Room j.

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


Sample Input 1

3

Sample Output 1

1 2
1

The following image describes this output:

For example, if we leave Room 2, traverse the path 2 \to 3 \to 2 \to 3 \to 2 \to 1 \to 2 while only passing passages of level 1 and get back to Room 2, we pass through a passage six times.

E - Card Collector

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800

問題文

HW 列に並んだマス目の上に合計 N 枚のカードが置かれています。

i 番目のカードには整数 A_i が書かれており、上から R_i 行目、左から C_i 列目のマスの上に置かれています。

同じマスに複数枚のカードが置かれていることもあります。

あなたは各行からそれぞれ 1 枚までカードを選んで取ります。

次に、各列からそれぞれ 1 枚までカードを選んで取ります。

取ったカードに書かれた整数の合計の最大値を求めてください。

制約

  • 入力は全て整数である。
  • 1 \leq N \leq 10^5
  • 1 \leq H, W \leq 10^5
  • 1 \leq A_i \leq 10^5
  • 1 \leq R_i \leq H
  • 1 \leq C_i \leq W

入力

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

N H W
R_1 C_1 A_1
R_2 C_2 A_2
\vdots
R_N C_N A_N

出力

取ったカードに書かれた整数の合計の最大値を出力せよ。


入力例 1

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

出力例 1

28

以下のように取ると、取ったカードに書かれた整数の合計は 28 になり、このときが最大です。

  • 1 行目から 4 番目のカードを取ります。
  • 2 行目から 6 番目のカードを取ります。
  • 1 列目から 2 番目のカードを取ります。
  • 2 列目から 5 番目のカードを取ります。

入力例 2

13 5 6
1 3 35902
4 6 19698
4 6 73389
3 6 3031
3 1 4771
1 4 4784
2 1 36357
2 1 24830
5 6 50219
4 6 22645
1 2 30739
1 4 68417
1 5 78537

出力例 2

430590

入力例 3

1 100000 100000
1 1 1

出力例 3

1

Score : 800 points

Problem Statement

There are N cards placed on a grid with H rows and W columns of squares.

The i-th card has an integer A_i written on it, and it is placed on the square at the R_i-th row from the top and the C_i-th column from the left.

Multiple cards may be placed on the same square.

You will first pick up at most one card from each row.

Then, you will pick up at most one card from each column.

Find the maximum possible sum of the integers written on the picked cards.

Constraints

  • All values are integers.
  • 1 \leq N \leq 10^5
  • 1 \leq H, W \leq 10^5
  • 1 \leq A_i \leq 10^5
  • 1 \leq R_i \leq H
  • 1 \leq C_i \leq W

Input

Input is given from Standard Input in the following format:

N H W
R_1 C_1 A_1
R_2 C_2 A_2
\vdots
R_N C_N A_N

Output

Print the maximum possible sum of the integers written on the picked cards.


Sample Input 1

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

Sample Output 1

28

The sum of the integers written on the picked cards will be 28, the maximum value possible, if you pick up cards as follows:

  • Pick up the fourth card from the first row.
  • Pick up the sixth card from the second row.
  • Pick up the second card from the first column.
  • Pick up the fifth card from the second column.

Sample Input 2

13 5 6
1 3 35902
4 6 19698
4 6 73389
3 6 3031
3 1 4771
1 4 4784
2 1 36357
2 1 24830
5 6 50219
4 6 22645
1 2 30739
1 4 68417
1 5 78537

Sample Output 2

430590

Sample Input 3

1 100000 100000
1 1 1

Sample Output 3

1
F - Candy Retribution

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000

問題文

次の条件を満たす長さ N の非負整数列 A_1, A_2, ..., A_N が何通りあるか求めてください。

  • L \leq A_1 + A_2 + ... + A_N \leq R
  • N 個の要素を降順に並べたとき、上から M 番目と M+1 番目の要素は等しい。

答えは非常に大きくなることがあるので、10^9+7 で割ったあまりを出力してください。

制約

  • 入力はすべて整数
  • 1 \leq M < N \leq 3 \times 10^5
  • 1 \leq L \leq R \leq 3 \times 10^5

入力

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

N M L R

出力

条件を満たす非負整数列の個数を 10^9+7 で割ったあまりを出力してください。


入力例 1

4 2 3 7

出力例 1

105

条件を満たす非負整数列は、

\begin{eqnarray} &(1, 1, 1, 0), (1, 1, 1, 1), (2, 1, 1, 0), (2, 1, 1, 1), (2, 2, 2, 0), (2, 2, 2, 1), \\ &(3, 0, 0, 0), (3, 1, 1, 0), (3, 1, 1, 1), (3, 2, 2, 0), (4, 0, 0, 0), (4, 1, 1, 0), \\ &(4, 1, 1, 1), (5, 0, 0, 0), (5, 1, 1, 0), (6, 0, 0, 0), (7, 0, 0, 0)\end{eqnarray}

およびこれらの並べ替え,105 通りです。


入力例 2

2 1 4 8

出力例 2

3

条件を満たす非負整数列は (2, 2), (3, 3), (4, 4)3 通りです。


入力例 3

141592 6535 89793 238462

出力例 3

933832916

Score: 1000 points

Problem Statement

Find the number of sequences of N non-negative integers A_1, A_2, ..., A_N that satisfy the following conditions:

  • L \leq A_1 + A_2 + ... + A_N \leq R
  • When the N elements are sorted in non-increasing order, the M-th and (M+1)-th elements are equal.

Since the answer can be enormous, print it modulo 10^9+7.

Constraints

  • All values in input are integers.
  • 1 \leq M < N \leq 3 \times 10^5
  • 1 \leq L \leq R \leq 3 \times 10^5

Input

Input is given from Standard Input in the following format:

N M L R

Output

Print the number of sequences of N non-negative integers, modulo 10^9+7.


Sample Input 1

4 2 3 7

Sample Output 1

105

The sequences of non-negative integers that satisfy the conditions are:

\begin{eqnarray} &(1, 1, 1, 0), (1, 1, 1, 1), (2, 1, 1, 0), (2, 1, 1, 1), (2, 2, 2, 0), (2, 2, 2, 1), \\ &(3, 0, 0, 0), (3, 1, 1, 0), (3, 1, 1, 1), (3, 2, 2, 0), (4, 0, 0, 0), (4, 1, 1, 0), \\ &(4, 1, 1, 1), (5, 0, 0, 0), (5, 1, 1, 0), (6, 0, 0, 0), (7, 0, 0, 0)\end{eqnarray}

and their permutations, for a total of 105 sequences.


Sample Input 2

2 1 4 8

Sample Output 2

3

The three sequences that satisfy the conditions are (2, 2), (3, 3), and (4, 4).


Sample Input 3

141592 6535 89793 238462

Sample Output 3

933832916