Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
整数 N があります。
2, 3, \ldots, N のどれで割っても 1 余る、N 以上 10^{13} 以下の整数を 1 つ出力してください。
この問題の制約下では、そのような整数は必ず 1 つ以上存在します。
制約
- 入力は全て整数
- 2 \leq N \leq 30
入力
入力は以下の形式で標準入力から与えられる。
N
出力
2, 3, \ldots, N のどれで割っても 1 余る、N 以上 10^{13} 以下の整数を 1 つ出力せよ。
そのような整数が複数存在する場合、どれを出力しても構わない。
入力例 1
3
出力例 1
7
7 を 2 で割った余りは 1、7 を 3 で割った余りは 1 です。
7 は 3 以上 10^{13} 以下の整数なので、条件を満たします。
入力例 2
10
出力例 2
39916801
Score : 300 points
Problem Statement
We have an integer N.
Print an integer x between N and 10^{13} (inclusive) such that, for every integer y between 2 and N (inclusive), the remainder when x is divided by y is 1.
Under the constraints of this problem, there is always at least one such integer x.
Constraints
- All values in input are integers.
- 2 \leq N \leq 30
Input
Input is given from Standard Input in the following format:
N
Output
Print an integer x between N and 10^{13} (inclusive) such that, for every integer y between 2 and N (inclusive), the remainder when x is divided by y is 1.
If there are multiple such integers, any of them will be accepted.
Sample Input 1
3
Sample Output 1
7
The remainder when 7 is divided by 2 is 1, and the remainder when 7 is divided by 3 is 1, too.
7 is an integer between 3 and 10^{13}, so this is a desirable output.
Sample Input 2
10
Sample Output 2
39916801
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
110
を 10^{10} 個連結した文字列を S とします(たとえば 110
を 3 個連結した文字列は 110110110
です)。
長さ N の文字列 T があります。
S に T が連続する部分文字列としていくつ含まれるかを求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- T は
0
,1
からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N T
出力
S に T が連続する部分文字列としていくつ含まれるかを出力せよ。
入力例 1
4 1011
出力例 1
9999999999
S は長いので、110
を 3 個連結した 110110110
に 1011
がいくつ含まれるかを考えます。
すると、
-
1
1011
0110 -
1101
1011
0
の 2 箇所に、1011
が連続する部分文字列として含まれています。
入力例 2
22 1011011011011011011011
出力例 2
9999999993
Score : 400 points
Problem Statement
Let S be the concatenation of 10^{10} copies of the string 110
. (For reference, the concatenation of 3 copies of 110
is 110110110
.)
We have a string T of length N.
Find the number of times T occurs in S as a contiguous substring.
Constraints
- 1 \leq N \leq 2 \times 10^5
- T is a string of length N consisting of
0
and1
.
Input
Input is given from Standard Input in the following format:
N T
Output
Print the number of times T occurs in S as a contiguous substring.
Sample Input 1
4 1011
Sample Output 1
9999999999
S is so long, so let us instead count the number of times 1011
occurs in the concatenation of 3 copies of 110
, that is, 110110110
. We can see it occurs twice:
-
1
1011
0110 -
1101
1011
0
Sample Input 2
22 1011011011011011011011
Sample Output 2
9999999993
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
1, 2, \ldots, N を並び替えた数列 P = P_1, P_2, \ldots, P_N があります。
あなたは P に対して、以下の N - 1 種類の操作を、任意の順番でちょうど 1 回ずつ行わなければなりません。
-
P_1 と P_2 を入れ替える
-
P_2 と P_3 を入れ替える
\vdots
-
P_{N - 1} と P_N を入れ替える
操作の順番を適切に決めることで、P を昇順に並び替えてください。
もしそれが不可能な場合、-1
を出力してください。
制約
- 入力は全て整数
- 2 \leq N \leq 2 \times 10^5
- P は 1, 2, \ldots, N を並び替えた数列
入力
入力は以下の形式で標準入力から与えられる。
N P_1 P_2 \ldots P_N
出力
どのような順番で操作しても P を昇順に並び替えることができない場合、-1
を出力せよ。
P を昇順に並び替えることができる場合、そのような操作列を N - 1 行使って出力せよ。 i ~ (1 \leq i \leq N - 1) 行目には、i 回目の操作で P_j と P_{j + 1} を入れ替えるとして、j を出力せよ。
P を昇順に並び替える操作列が複数存在する場合、どれを出力しても構わない。
入力例 1
5 2 4 1 5 3
出力例 1
4 2 3 1
以下のような操作列が P を昇順に並び替えます。
- まず P_4 と P_5 を入れ替える。P は 2, 4, 1, 3, 5 になる
- 次に P_2 と P_3 を入れ替える。P は 2, 1, 4, 3, 5 になる
- 次に P_3 と P_4 を入れ替える。P は 2, 1, 3, 4, 5 になる
- 次に P_1 と P_2 を入れ替える。P は 1, 2, 3, 4, 5 になる
入力例 2
5 5 4 3 2 1
出力例 2
-1
Score : 500 points
Problem Statement
We have a permutation P = P_1, P_2, \ldots, P_N of 1, 2, \ldots, N.
You have to do the following N - 1 operations on P, each exactly once, in some order:
-
Swap P_1 and P_2.
-
Swap P_2 and P_3.
\vdots
-
Swap P_{N-1} and P_N.
Your task is to sort P in ascending order by configuring the order of operations.
If it is impossible, print -1
instead.
Constraints
- All values in input are integers.
- 2 \leq N \leq 2 \times 10^5
- P is a permutation of 1, 2, \ldots, N.
Input
Input is given from Standard Input in the following format:
N P_1 P_2 \ldots P_N
Output
If it is impossible to sort P in ascending order by configuring the order of operations, print -1
.
Otherwise, print N-1 lines to represent a sequence of operations that sorts P in ascending order. The i-th line (1 \leq i \leq N - 1) should contain j, where the i-th operation swaps P_j and P_{j + 1}.
If there are multiple such sequences of operations, any of them will be accepted.
Sample Input 1
5 2 4 1 5 3
Sample Output 1
4 2 3 1
The following sequence of operations sort P in ascending order:
- First, swap P_4 and P_5, turning P into 2, 4, 1, 3, 5.
- Then, swap P_2 and P_3, turning P into 2, 1, 4, 3, 5.
- Then, swap P_3 and P_4, turning P into 2, 1, 3, 4, 5.
- Finally, swap P_1 and P_2, turning P into 1, 2, 3, 4, 5.
Sample Input 2
5 5 4 3 2 1
Sample Output 2
-1
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
長さが N の非負整数列 A があります。
長さが N で、和が M 以下である任意の非負整数列 B について、\prod _{i = 1} ^N \dbinom{B_i}{A_i} の値を計算し、その総和を 10^9 + 7 で割った余りを出力してください。
ここで \dbinom{B_i}{A_i} は、B_i 個のものの中から A_i 個のものを選ぶ場合の数(二項係数)であり、B_i < A_i のときは 0 です。
制約
- 入力は全て整数
- 1 \leq N \leq 2000
- 1 \leq M \leq 10^9
- 0 \leq A_i \leq 2000
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \ldots A_N
出力
\prod _{i = 1} ^N \dbinom{B_i}{A_i} の総和を 10^9 + 7 で割った余りを出力せよ。
入力例 1
3 5 1 2 1
出力例 1
8
\prod _{i = 1} ^N \dbinom{B_i}{A_i} が 1 以上となるような数列 B の定め方は、以下の 4 通りです。
-
B = 1, 2, 1 とする。このとき \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{2}{2} \times \dbinom{1}{1} = 1 である
-
B = 2, 2, 1 とする。このとき \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{2}{1} \times \dbinom{2}{2} \times \dbinom{1}{1} = 2 である
-
B = 1, 3, 1 とする。このとき \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{3}{2} \times \dbinom{1}{1} = 3 である
-
B = 1, 2, 2 とする。このとき \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{2}{2} \times \dbinom{2}{1} = 2 である
よって答えは 1 + 2 + 3 + 2 = 8 です。
入力例 2
10 998244353 31 41 59 26 53 58 97 93 23 84
出力例 2
642612171
Score : 600 points
Problem Statement
We have a sequence A of N non-negative integers.
Compute the sum of \prod _{i = 1} ^N \dbinom{B_i}{A_i} over all sequences B of N non-negative integers whose sum is at most M, and print it modulo (10^9 + 7).
Here, \dbinom{B_i}{A_i}, the binomial coefficient, denotes the number of ways to choose A_i objects from B_i objects, and is 0 when B_i < A_i.
Constraints
- All values in input are integers.
- 1 \leq N \leq 2000
- 1 \leq M \leq 10^9
- 0 \leq A_i \leq 2000
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 \ldots A_N
Output
Print the sum of \prod _{i = 1} ^N \dbinom{B_i}{A_i}, modulo (10^9 + 7).
Sample Input 1
3 5 1 2 1
Sample Output 1
8
There are four sequences B such that \prod _{i = 1} ^N \dbinom{B_i}{A_i} is at least 1:
-
B = \{1, 2, 1\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{2}{2} \times \dbinom{1}{1} = 1;
-
B = \{2, 2, 1\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{2}{1} \times \dbinom{2}{2} \times \dbinom{1}{1} = 2;
-
B = \{1, 3, 1\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{3}{2} \times \dbinom{1}{1} = 3;
-
B = \{1, 2, 2\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{2}{2} \times \dbinom{2}{1} = 2.
The sum of these is 1 + 2 + 3 + 2 = 8.
Sample Input 2
10 998244353 31 41 59 26 53 58 97 93 23 84
Sample Output 2
642612171
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
A
, B
, C
からなる長さ N の文字列 S があります。
あなたは S に対して、以下の操作を 0 回以上行うことができます。
- S_i \neq S_{i + 1} である i ~ (1 \leq i \leq |S| - 1) を選ぶ。S_i を S_i, S_{i + 1} のいずれとも(
A
,B
,C
の中で)異なる文字で置き換え、S_{i + 1} を S から削除する
操作を 0 回以上行ったあとの S として、ありえるものの種類数を 10^9+7 で割った余りを出力してください。
制約
- 1 \leq N \leq 10^6
- S は
A
,B
,C
からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
操作を 0 回以上行ったあとの S として、ありえるものの種類数を 10^9+7 で割った余りを出力せよ。
入力例 1
5 ABAAC
出力例 1
11
たとえば以下のように操作すると、文字列 S として ACB
が得られます。
- まず i として 2 を選ぶ。S_2 を
C
で置き換え、S_3 を削除するので S はACAC
になる - 次に i として 3 を選ぶ。S_3 を
B
で置き換え、S_4 を削除するので S はACB
になる
入力例 2
50 AACCCCBBBACCCCABABCCCCABACCACACACCACABABBBABABACCB
出力例 2
256972022
Score : 800 points
Problem Statement
We have a string S of length N consisting of A
, B
, and C
.
You can do the following operation on S zero or more times:
- Choose i (1 \leq i \leq |S| - 1) such that S_i \neq S_{i + 1}. Replace S_i with the character (among
A
,B
, andC
) that is different from both S_i and S_{i + 1}, and remove S_{i + 1} from S.
Find the number of distinct strings that S can be after zero or more operations, and print the count modulo (10^9+7).
Constraints
- 1 \leq N \leq 10^6
- S is a string of length N consisting of
A
,B
, andC
.
Input
Input is given from Standard Input in the following format:
N S
Output
Print the number of distinct strings that S can be after zero or more operations, modulo (10^9+7).
Sample Input 1
5 ABAAC
Sample Output 1
11
For example, the following sequence of operations turns S into ACB
:
- First, choose i=2. We replace S_2 with
C
and remove S_3, turning S intoACAC
. - Then, choose i=3. We replace S_3 with
B
and remove S_4, turning S intoACB
.
Sample Input 2
50 AACCCCBBBACCCCABABCCCCABACCACACACCACABABBBABABACCB
Sample Output 2
256972022
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
0, 1, \ldots, N - 1 を並び替えた数列 P = P_0, P_1, \ldots, P_{N - 1} があります。
あなたは P に対して、以下の操作を最大 2 \times 10^5 回まで行うことができます。
- 整数 i ~ (0 \leq i \leq N - 1) を宣言する。P_i と P_{(i + P_i) \textrm{ mod } N} を入れ替える
適切に操作を行うことで、P を昇順に並び替えてください。もしそれが不可能な場合、-1
を出力してください。
制約
- 入力は全て整数
- 2 \leq N \leq 100
- P は 0, 1, \ldots, N - 1 を並び替えた数列
入力
入力は以下の形式で標準入力から与えられる。
N P_0 P_1 \ldots P_{N - 1}
出力
2 \times 10^5 回以下の操作で P を昇順に並び替えることが不可能な場合、-1
を出力せよ。
2 \times 10^5 回以下の操作で P を昇順に並び替えることが可能な場合、K 回操作を行うとして、以下の形式で K + 1 行出力せよ。
- 1 行目は整数 K
- 1 + i~(1 \leq i \leq K) 行目は、i 回目の操作で宣言する整数 j ~ (0 \leq j \leq N - 1)
操作回数を最小化する必要はない。 また、2 \times 10^5 回以下の操作で P を昇順に並び替える操作列が複数存在する場合、どれを出力しても構わない。
入力例 1
8 7 1 2 6 4 0 5 3
出力例 1
4 6 0 3 0
この操作列は、以下のように P を昇順に並び替えます。
-
まず i として 6 を宣言し、P_6 (= 5) と P_{(6 + 5) \textrm{ mod } 8} = P_3 (= 6) を入れ替える。P は 7, 1, 2, 5, 4, 0, 6, 3 になる
-
次に i として 0 を宣言し、P_0 (= 7) と P_{(0 + 7) \textrm{ mod } 8} = P_7 (= 3) を入れ替える。P は 3, 1, 2, 5, 4, 0, 6, 7 になる
-
次に i として 3 を宣言し、P_3 (= 5) と P_{(3 + 5) \textrm{ mod } 8} = P_0 (= 3) を入れ替える。P は 5, 1, 2, 3, 4, 0, 6, 7 になる
-
次に i として 0 を宣言し、P_0 (= 5) と P_{(0 + 5) \textrm{ mod } 8} = P_5 (= 0) を入れ替える。P は 0, 1, 2, 3, 4, 5, 6, 7 になる
Score : 900 points
Problem Statement
We have a permutation P = P_0, P_1, \ldots, P_{N - 1} of 0, 1, \ldots, N - 1.
You can do the following operation on P at most 2 \times 10^5 times:
- Announce an integer i ~ (0 \leq i \leq N - 1). Swap P_i and P_{(i + P_i) \textrm{ mod } N}.
Your task is to sort P in ascending order with this operation.
If it is impossible, print -1
instead.
Constraints
- All values in input are integers.
- 2 \leq N \leq 100
- P is a permutation of 0, 1, \ldots, N - 1.
Input
Input is given from Standard Input in the following format:
N P_0 P_1 \ldots P_{N - 1}
Output
If it is impossible to sort P in ascending order with at most 2 \times 10^5 operations, print -1
.
Otherwise, print K + 1 lines to represent a sequence of operations that sorts P in ascending order, where K is the number of operations done, as follows:
- The first line should contain the integer K;
- the (1 + i)-the line (1 \leq i \leq K) should contain the integer j ~ (0 \leq j \leq N - 1) announced in the i-th operation.
You do not have to minimize the number of operations done. If there are multiple such sequences of at most 2 \times 10^5 operations, any of them will be accepted.
Sample Input 1
8 7 1 2 6 4 0 5 3
Sample Output 1
4 6 0 3 0
This sequence of operations sorts P in ascending order, as follows:
-
First, announce i = 6. We swap P_6 (= 5) and P_{(6 + 5) \textrm{ mod } 8} = P_3 (= 6), turning P into 7, 1, 2, 5, 4, 0, 6, 3.
-
Then, announce i = 0. We swap P_0 (= 7) and P_{(0 + 7) \textrm{ mod } 8} = P_7 (= 3), turning P into 3, 1, 2, 5, 4, 0, 6, 7.
-
Then, announce i = 3. We swap P_3 (= 5) and P_{(3 + 5) \textrm{ mod } 8} = P_0 (= 3), turning P into 5, 1, 2, 3, 4, 0, 6, 7.
-
Finally, announce i = 0. We swap P_0 (= 5) and P_{(0 + 5) \textrm{ mod } 8} = P_5 (= 0), turning P into 0, 1, 2, 3, 4, 5, 6, 7.