実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 300 点
問題文
整数 N が与えられます。 N! の正の約数の個数を 10^9+7 で割った余りを求めてください。
制約
- 1≦N≦10^3
入力
入力は以下の形式で標準入力から与えられる。
N
出力
N! の正の約数の個数を 10^9+7 で割った余りを出力せよ。
入力例 1
3
出力例 1
4
3! =6 です。6 の正の約数は 1,2,3,6 の 4 個なので、4 を出力します。
入力例 2
6
出力例 2
30
入力例 3
1000
出力例 3
972926972
Score : 300 points
Problem Statement
You are given an integer N. Find the number of the positive divisors of N!, modulo 10^9+7.
Constraints
- 1≤N≤10^3
Input
The input is given from Standard Input in the following format:
N
Output
Print the number of the positive divisors of N!, modulo 10^9+7.
Sample Input 1
3
Sample Output 1
4
There are four divisors of 3! =6: 1, 2, 3 and 6. Thus, the output should be 4.
Sample Input 2
6
Sample Output 2
30
Sample Input 3
1000
Sample Output 3
972926972
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 500 点
問題文
東西方向にのびる直線上に、N 個の町があります。 町には、西から順に 1 から N までの番号がついています。 直線上には座標が設定されていて、東に行くほど座標が大きくなります。 町 i の座標は X_i です。
あなたは今、町 1 にいて、これからほかの全ての町を訪れたいです。 移動する手段は次の 2 種類あります。
-
直線上を歩いて移動する。 東西どちらに歩いても、1 移動する度に疲労度が A 上がります。
-
好きな場所へテレポートする。 テレポートをすると、移動した距離によらず疲労度が B 上がります。
この 2 種類の移動を繰り返して全ての町を最適に回った時、疲労度の上昇値の合計の最小値がいくつになるか求めてください。
制約
- 入力は全て整数である
- 2≦N≦10^5
- 1≦X_i≦10^9
- 全ての i(1≦i≦N-1) について、X_i<X_{i+1} が成り立つ
- 1≦A≦10^9
- 1≦B≦10^9
入力
入力は以下の形式で標準入力から与えられる。
N A B X_1 X_2 ... X_N
出力
全ての町を最適に回った時、疲労度の上昇値の合計の最小値がいくつになるかを出力せよ。
入力例 1
4 2 5 1 2 5 7
出力例 1
11
町 1 から町 2 まで 1 の距離歩いて移動したあと、町 3 にテレポートし、そこから町 4 まで 2 の距離歩いて移動すると、 疲労度の上昇値の合計が 2×1+5+2×2=11 になり、これが最小です。
入力例 2
7 1 100 40 43 45 105 108 115 124
出力例 2
84
町 1 から町 7 まで歩き続けると、疲労度の上昇値の合計が 84 になり、これが最小です。
入力例 3
7 1 2 24 35 40 68 72 99 103
出力例 3
12
どのような順番でもよいので、6 回のテレポートで全ての町を訪れると、疲労度の上昇値の合計が 12 になり、これが最小です。
Score : 500 points
Problem Statement
There are N towns on a line running east-west. The towns are numbered 1 through N, in order from west to east. Each point on the line has a one-dimensional coordinate, and a point that is farther east has a greater coordinate value. The coordinate of town i is X_i.
You are now at town 1, and you want to visit all the other towns. You have two ways to travel:
-
Walk on the line. Your fatigue level increases by A each time you travel a distance of 1, regardless of direction.
-
Teleport to any location of your choice. Your fatigue level increases by B, regardless of the distance covered.
Find the minimum possible total increase of your fatigue level when you visit all the towns in these two ways.
Constraints
- All input values are integers.
- 2≤N≤10^5
- 1≤X_i≤10^9
- For all i(1≤i≤N-1), X_i<X_{i+1}.
- 1≤A≤10^9
- 1≤B≤10^9
Input
The input is given from Standard Input in the following format:
N A B X_1 X_2 ... X_N
Output
Print the minimum possible total increase of your fatigue level when you visit all the towns.
Sample Input 1
4 2 5 1 2 5 7
Sample Output 1
11
From town 1, walk a distance of 1 to town 2, then teleport to town 3, then walk a distance of 2 to town 4. The total increase of your fatigue level in this case is 2×1+5+2×2=11, which is the minimum possible value.
Sample Input 2
7 1 100 40 43 45 105 108 115 124
Sample Output 2
84
From town 1, walk all the way to town 7. The total increase of your fatigue level in this case is 84, which is the minimum possible value.
Sample Input 3
7 1 2 24 35 40 68 72 99 103
Sample Output 3
12
Visit all the towns in any order by teleporting six times. The total increase of your fatigue level in this case is 12, which is the minimum possible value.
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 600 点
問題文
1 から N までの番号のついた N 人の人がいます。 以下の二つの条件を満たすように、彼らをいくつかのグループに分けたいです。
-
どのグループも、そのグループに含まれる人数が A 人以上 B 人以下である。
-
ちょうど i 人の人が含まれるようなグループの数を F_i で表したとき、 すべての i について、F_i=0 または C≦F_i≦D が成り立っている。
このようなグループ分けが何通りあり得るか求めてください。 ただし、ある二つのグループ分けが異なるとは、二人の人の組であって、 片方のグループ分けでは同じグループに含まれ、他方では同じグループに含まれないようなものが存在することを意味します。 なお、答えは非常に大きくなることがあるので、10^9+7 で割った余りを出力してください。
制約
- 1≦N≦10^3
- 1≦A≦B≦N
- 1≦C≦D≦N
入力
入力は以下の形式で標準入力から与えられる。
N A B C D
出力
あり得るグループ分けの個数を、10^9+7 で割った余りを出力せよ。
入力例 1
3 1 3 1 2
出力例 1
4
以下の 4 通りの分け方があります。
- (1,2),(3)
- (1,3),(2)
- (2,3),(1)
- (1,2,3)
(1),(2),(3) のような分け方は、一つ目の条件は満たしていますが、 二つ目の条件を満たしていないために数えられません。
入力例 2
7 2 3 1 3
出力例 2
105
2 人グループ、2 人グループ、3 人グループの三つに分ける以外に適切な分け方はありません。 そして、このような分け方は 105 通りあります。
入力例 3
1000 1 1000 1 1000
出力例 3
465231251
入力例 4
10 3 4 2 5
出力例 4
0
答えが 0 になることもあり得ます。
Score : 600 points
Problem Statement
There are N people, conveniently numbered 1 through N. We want to divide them into some number of groups, under the following two conditions:
-
Every group contains between A and B people, inclusive.
-
Let F_i be the number of the groups containing exactly i people. Then, for all i, either F_i=0 or C≤F_i≤D holds.
Find the number of these ways to divide the people into groups. Here, two ways to divide them into groups is considered different if and only if there exists two people such that they belong to the same group in exactly one of the two ways. Since the number of these ways can be extremely large, print the count modulo 10^9+7.
Constraints
- 1≤N≤10^3
- 1≤A≤B≤N
- 1≤C≤D≤N
Input
The input is given from Standard Input in the following format:
N A B C D
Output
Print the number of ways to divide the people into groups under the conditions, modulo 10^9+7.
Sample Input 1
3 1 3 1 2
Sample Output 1
4
There are four ways to divide the people:
- (1,2),(3)
- (1,3),(2)
- (2,3),(1)
- (1,2,3)
The following way to divide the people does not count: (1),(2),(3). This is because it only satisfies the first condition and not the second.
Sample Input 2
7 2 3 1 3
Sample Output 2
105
The only ways to divide the people under the conditions are the ones where there are two groups of two people, and one group of three people. There are 105 such ways.
Sample Input 3
1000 1 1000 1 1000
Sample Output 3
465231251
Sample Input 4
10 3 4 2 5
Sample Output 4
0
The answer can be 0.
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 1000 点
問題文
1 から N までの番号のついた N 軒の焼肉店があります。 焼肉店は番号順に一直線上に並んでいて、i 番目の焼肉店と i+1 番目の焼肉店の距離は A_i です。
joisinoお姉ちゃんは、1 から M までの番号のついた M 枚のチケットを持っています。 どの焼肉店でも、これらのチケットと引き換えに焼き肉を食べられます。 i 番目の焼肉店で、j 番目のチケットと引き換えに食べられる焼き肉の美味しさは B_{i,j} です。 一度使ったチケットは 2 度以上使えません。 また、同じ焼肉店で使うチケットの数に制限はありません。
joisinoお姉ちゃんは、適当な焼肉店の前からスタートして、別の焼肉店の場所へ移動したり、 目の前にある焼肉店でまだ使っていないチケットを使って焼き肉を食べたりすることを繰り返して、M 枚の焼き肉を食べようとしています。 joisinoお姉ちゃんの最終的な幸福度は、「食べた焼き肉の美味しさの総和 - 移動した距離の合計」で求められます。 joisinoお姉ちゃんの最終的な幸福度の最大値を求めてください。
制約
- 入力は全て整数である
- 2≦N≦5×10^3
- 1≦M≦200
- 1≦A_i≦10^9
- 1≦B_{i,j}≦10^9
入力
入力は以下の形式で標準入力から与えられる。
N M
A_1 A_2 ... A_{N-1}
B_{1,1} B_{1,2} ... B_{1,M}
B_{2,1} B_{2,2} ... B_{2,M}
:
B_{N,1} B_{N,2} ... B_{N,M}
出力
joisinoお姉ちゃんの最終的な幸福度の最大値を出力せよ。
入力例 1
3 4 1 4 2 2 5 1 1 3 3 2 2 2 5 1
出力例 1
11
1 番目の焼肉店の前からスタートし、1 番目と 3 番目のチケットを使って焼き肉を食べたあと、 2 番目の焼肉店の前まで移動して、2 番目と 4 番目のチケットを使って焼き肉を食べると、幸福度を最大化できます。
入力例 2
5 3 1 2 3 4 10 1 1 1 1 1 1 10 1 1 1 1 1 1 10
出力例 2
20
Score : 1000 points
Problem Statement
There are N barbecue restaurants along a street. The restaurants are numbered 1 through N from west to east, and the distance between restaurant i and restaurant i+1 is A_i.
Joisino has M tickets, numbered 1 through M. Every barbecue restaurant offers barbecue meals in exchange for these tickets. Restaurant i offers a meal of deliciousness B_{i,j} in exchange for ticket j. Each ticket can only be used once, but any number of tickets can be used at a restaurant.
Joisino wants to have M barbecue meals by starting from a restaurant of her choice, then repeatedly traveling to another barbecue restaurant and using unused tickets at the restaurant at her current location. Her eventual happiness is calculated by the following formula: "(The total deliciousness of the meals eaten) - (The total distance traveled)". Find her maximum possible eventual happiness.
Constraints
- All input values are integers.
- 2≤N≤5×10^3
- 1≤M≤200
- 1≤A_i≤10^9
- 1≤B_{i,j}≤10^9
Input
The input is given from Standard Input in the following format:
N M
A_1 A_2 ... A_{N-1}
B_{1,1} B_{1,2} ... B_{1,M}
B_{2,1} B_{2,2} ... B_{2,M}
:
B_{N,1} B_{N,2} ... B_{N,M}
Output
Print Joisino's maximum possible eventual happiness.
Sample Input 1
3 4 1 4 2 2 5 1 1 3 3 2 2 2 5 1
Sample Output 1
11
The eventual happiness can be maximized by the following strategy: start from restaurant 1 and use tickets 1 and 3, then move to restaurant 2 and use tickets 2 and 4.
Sample Input 2
5 3 1 2 3 4 10 1 1 1 1 1 1 10 1 1 1 1 1 1 10
Sample Output 2
20