実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 100 点
問題文
すぬけ君は 1,2,\ldots,N の N 個の整数を持っています。 すぬけ君はこれらの整数から K 個の整数を選んで高橋君にあげようと考えています。
連続する K 個の整数を選ぶ方法は何通りありますか?
制約
- 入力は全て整数
- 1 \leq K \leq N \leq 50
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
答えを出力せよ。
入力例 1
3 2
出力例 1
2
- 連続する 2 個の整数を選ぶ方法は (1,2) と (2,3) の 2 通りです。
入力例 2
13 3
出力例 2
11
Score : 100 points
Problem Statement
Snuke has N integers: 1,2,\ldots,N. He will choose K of them and give those to Takahashi.
How many ways are there to choose K consecutive integers?
Constraints
- All values in input are integers.
- 1 \leq K \leq N \leq 50
Input
Input is given from Standard Input in the following format:
N K
Output
Print the answer.
Sample Input 1
3 2
Sample Output 1
2
There are two ways to choose two consecutive integers: (1,2) and (2,3).
Sample Input 2
13 3
Sample Output 2
11
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 200 点
問題文
すぬけ君はボールが入った箱を売っている店に行きました。 売っている箱は以下の 3 種類です。
- R 個のボールが入った赤色の箱
- G 個のボールが入った緑色の箱
- B 個のボールが入った青色の箱
すぬけ君は赤色の箱を r 個、緑色の箱を g 個、青色の箱を b 個買うことで合計でちょうど N 個のボールが手に入るようにしたいです。 これを達成する非負整数の組 (r,g,b) はいくつありますか?
制約
- 入力は全て整数
- 1 \leq R,G,B,N \leq 3000
入力
入力は以下の形式で標準入力から与えられる。
R G B N
出力
答えを出力せよ。
入力例 1
1 2 3 4
出力例 1
4
条件を満たすのは以下の 4 通りです。
- (4,0,0)
- (2,1,0)
- (1,0,1)
- (0,2,0)
入力例 2
13 1 4 3000
出力例 2
87058
Score : 200 points
Problem Statement
Snuke has come to a store that sells boxes containing balls. The store sells the following three kinds of boxes:
- Red boxes, each containing R red balls
- Green boxes, each containing G green balls
- Blue boxes, each containing B blue balls
Snuke wants to get a total of exactly N balls by buying r red boxes, g green boxes and b blue boxes. How many triples of non-negative integers (r,g,b) achieve this?
Constraints
- All values in input are integers.
- 1 \leq R,G,B,N \leq 3000
Input
Input is given from Standard Input in the following format:
R G B N
Output
Print the answer.
Sample Input 1
1 2 3 4
Sample Output 1
4
Four triples achieve the objective, as follows:
- (4,0,0)
- (2,1,0)
- (1,0,1)
- (0,2,0)
Sample Input 2
13 1 4 3000
Sample Output 2
87058
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
すぬけ君は N 個の文字列を持っています。i 番目の文字列は s_i です。
これらの文字列を好きな順序で並べたあと、連結して 1 つの文字列を作ることを考えます。
作った文字列に AB
という部分文字列が含まれる個数としてありうる値のうち、最大値を求めてください。
制約
- 1 \leq N \leq 10^{4}
- 2 \leq |s_i| \leq 10
- s_i は英大文字のみからなる
入力
入力は以下の形式で標準入力から与えられる。
N s_1 \vdots s_N
出力
答えを出力せよ。
入力例 1
3 ABCA XBAZ BAD
出力例 1
2
- 例えば、
ABCA
,BAD
,XBAZ
の順で連結してABCABADXBAZ
を作ったとき、AB
という部分文字列は 2 つ含まれます。
入力例 2
9 BEWPVCRWH ZZNQYIJX BAVREA PA HJMYITEOX BCJHMRMNK BP QVFABZ PRGKSPUNA
出力例 2
4
入力例 3
7 RABYBBE JOZ BMHQUVA BPA ISU MCMABAOBHZ SZMEHMA
出力例 3
4
Score : 400 points
Problem Statement
Snuke has N strings. The i-th string is s_i.
Let us concatenate these strings into one string after arranging them in some order.
Find the maximum possible number of occurrences of AB
in the resulting string.
Constraints
- 1 \leq N \leq 10^{4}
- 2 \leq |s_i| \leq 10
- s_i consists of uppercase English letters.
Input
Input is given from Standard Input in the following format:
N s_1 \vdots s_N
Output
Print the answer.
Sample Input 1
3 ABCA XBAZ BAD
Sample Output 1
2
For example, if we concatenate ABCA
, BAD
and XBAZ
in this order, the resulting string ABCABADXBAZ
has two occurrences of AB
.
Sample Input 2
9 BEWPVCRWH ZZNQYIJX BAVREA PA HJMYITEOX BCJHMRMNK BP QVFABZ PRGKSPUNA
Sample Output 2
4
Sample Input 3
7 RABYBBE JOZ BMHQUVA BPA ISU MCMABAOBHZ SZMEHMA
Sample Output 3
4
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
すぬけ君は高橋君から正の整数 N をもらいました。 正の整数 m が以下の条件を満たすとき、 お気に入りの数 と呼ばれます。
- N を m で割った商とあまりが等しい、すなわち \lfloor \frac{N}{m} \rfloor = N \bmod m が成立する
お気に入りの数を全て求め、その総和を出力してください。
制約
- 入力は全て整数
- 1 \leq N \leq 10^{12}
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
8
出力例 1
10
- お気に入りの数は 3 と 7 の 2 つです。これらの総和である 10 を出力してください。
入力例 2
1000000000000
出力例 2
2499686339916
- オーバーフローに注意してください。
Score : 500 points
Problem Statement
Snuke received a positive integer N from Takahashi. A positive integer m is called a favorite number when the following condition is satisfied:
- The quotient and remainder of N divided by m are equal, that is, \lfloor \frac{N}{m} \rfloor = N \bmod m holds.
Find all favorite numbers and print the sum of those.
Constraints
- All values in input are integers.
- 1 \leq N \leq 10^{12}
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
8
Sample Output 1
10
There are two favorite numbers: 3 and 7. Print the sum of these, 10.
Sample Input 2
1000000000000
Sample Output 2
2499686339916
Watch out for overflow.
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 800 点
問題文
長さ n の数列 a の 美しさ を a_1 \oplus a_2 \oplus \cdots \oplus a_{n} で定義します。ここで \oplus はビットごとの排他的論理和を表します。
長さ N の数列 A が与えられます。 すぬけ君は A に 0 個以上の仕切りを入れて、いくつかの空でない連続する部分列に分割しようとしています。
仕切りを入れる方法は 2^{N-1} 通りあります。 それらのうち、分割された数列たちの美しさが全て等しくなるものの個数を 10^{9}+7 で割ったあまりを求めてください。
制約
- 入力は全て整数
- 1 \leq N \leq 5 \times 10^5
- 0 \leq A_i < 2^{20}
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_{N}
出力
答えを出力せよ。
入力例 1
3 1 2 3
出力例 1
3
条件を満たす分割方法は以下の 3 通りです。(1),(2),(3) と分割したときに限り、全ての美しさが等しくなりません。
- (1,2,3)
- (1),(2,3)
- (1,2),(3)
入力例 2
3 1 2 2
出力例 2
1
入力例 3
32 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
出力例 3
147483634
- 条件を満たすものの個数を 10^{9}+7 で割ったあまりを求めてください。
入力例 4
24 1 2 5 3 3 6 1 1 8 8 0 3 3 4 6 6 4 0 7 2 5 4 6 2
出力例 4
292
Score : 800 points
Problem Statement
The beauty of a sequence a of length n is defined as a_1 \oplus \cdots \oplus a_n, where \oplus denotes the bitwise exclusive or (XOR).
You are given a sequence A of length N. Snuke will insert zero or more partitions in A to divide it into some number of non-empty contiguous subsequences.
There are 2^{N-1} possible ways to insert partitions. How many of them divide A into sequences whose beauties are all equal? Find this count modulo 10^{9}+7.
Constraints
- All values in input are integers.
- 1 \leq N \leq 5 \times 10^5
- 0 \leq A_i < 2^{20}
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_{N}
Output
Print the answer.
Sample Input 1
3 1 2 3
Sample Output 1
3
Four ways of dividing A shown below satisfy the condition. The condition is not satisfied only if A is divided into (1),(2),(3).
- (1,2,3)
- (1),(2,3)
- (1,2),(3)
Sample Input 2
3 1 2 2
Sample Output 2
1
Sample Input 3
32 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Sample Output 3
147483634
Find the count modulo 10^{9}+7.
Sample Input 4
24 1 2 5 3 3 6 1 1 8 8 0 3 3 4 6 6 4 0 7 2 5 4 6 2
Sample Output 4
292
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 1200 点
問題文
N 個の頂点と、M 本の辺からなる単純かつ連結な無向グラフ G が与えられます。 頂点には 1 から N の番号が、辺には 1 から M の番号がついています。
辺 i は頂点 a_i と b_i を双方向につなぐ辺です。 ここで、頂点 1,2,\ldots,N と辺 1,2,\ldots,N-1 からなる部分グラフが G の全域木となることが保証されます。
頂点 1,2,\ldots,N と辺 1,2,\ldots,N-1 からなる木が G の最小全域木となるような辺への重みの割り当て方を 良い割り当て と呼びます。
それぞれの辺に 1 から M までの相異なる整数の重みを割り当てる方法は M! 通りあります。 それらのうち、良い割り当てであるようなもの全てについて最小全域木に含まれる辺の重みの和を求め、それらの総和を 10^{9}+7 で割ったあまりを出力してください。
制約
- 入力は全て整数
- 2 \leq N \leq 20
- N-1 \leq M \leq N(N-1)/2
- 1 \leq a_i, b_i \leq N
- G に自己ループや多重辺は存在しない
- 頂点 1,2,\ldots,N と辺 1,2,\ldots,N-1 からなる部分グラフは G の全域木となる
入力
入力は以下の形式で標準入力から与えられる。
N M a_1 b_1 \vdots a_M b_M
出力
答えを出力せよ。
入力例 1
3 3 1 2 2 3 1 3
出力例 1
6
- 辺 3 に重み 3 が割り当てられたときに限り、良い割り当てとなります。
- これらの良い割り当てにおける G の最小全域木に含まれる辺の重みの和は 3 であり、良い割り当ての個数は 2 つなので答えは 6 となります。
入力例 2
4 4 1 2 3 2 3 4 1 3
出力例 2
50
入力例 3
15 28 10 7 5 9 2 13 2 14 6 1 5 12 2 10 3 9 10 15 11 12 12 6 2 12 12 8 4 10 15 3 13 14 1 15 15 12 4 14 1 7 5 11 7 13 9 10 2 7 1 9 5 6 12 14 5 2
出力例 3
657573092
- 総和を 10^{9}+7 で割ったあまりを出力してください。
Score : 1200 points
Problem Statement
You are given a simple connected undirected graph G consisting of N vertices and M edges. The vertices are numbered 1 to N, and the edges are numbered 1 to M.
Edge i connects Vertex a_i and b_i bidirectionally. It is guaranteed that the subgraph consisting of Vertex 1,2,\ldots,N and Edge 1,2,\ldots,N-1 is a spanning tree of G.
An allocation of weights to the edges is called a good allocation when the tree consisting of Vertex 1,2,\ldots,N and Edge 1,2,\ldots,N-1 is a minimum spanning tree of G.
There are M! ways to allocate the edges distinct integer weights between 1 and M. For each good allocation among those, find the total weight of the edges in the minimum spanning tree, and print the sum of those total weights modulo 10^{9}+7.
Constraints
- All values in input are integers.
- 2 \leq N \leq 20
- N-1 \leq M \leq N(N-1)/2
- 1 \leq a_i, b_i \leq N
- G does not have self-loops or multiple edges.
- The subgraph consisting of Vertex 1,2,\ldots,N and Edge 1,2,\ldots,N-1 is a spanning tree of G.
Input
Input is given from Standard Input in the following format:
N M a_1 b_1 \vdots a_M b_M
Output
Print the answer.
Sample Input 1
3 3 1 2 2 3 1 3
Sample Output 1
6
An allocation is good only if Edge 3 has the weight 3. For these good allocations, the total weight of the edges in the minimum spanning tree is 3, and there are two good allocations, so the answer is 6.
Sample Input 2
4 4 1 2 3 2 3 4 1 3
Sample Output 2
50
Sample Input 3
15 28 10 7 5 9 2 13 2 14 6 1 5 12 2 10 3 9 10 15 11 12 12 6 2 12 12 8 4 10 15 3 13 14 1 15 15 12 4 14 1 7 5 11 7 13 9 10 2 7 1 9 5 6 12 14 5 2
Sample Output 3
657573092
Print the sum of those total weights modulo 10^{9}+7.