Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
長さ N の文字列 S が与えられます。 S の部分列であって、すべて異なる文字からなるものの数を 10^9+7 で割った余りを答えてください。文字列として同一でも、異なる位置から取り出された部分列は区別して数えることとします。
ただし、文字列の部分列とは、文字列から文字をいくつか 正の個数 取り出し、もとの文字列から順序を変えずにつなげたものを指します。
制約
- 1 \leq N \leq 100000
- S は英小文字からなる
- |S|=N
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
異なる文字からなる部分列の個数を 10^9+7 で割った余りを出力せよ。
入力例 1
4 abcd
出力例 1
15
S 自体がすべて異なる文字からなるので、すべての部分列が条件を満たします。
入力例 2
3 baa
出力例 2
5
b
, a
(2 通り), ba
(2 通り) の合計 5 通りが答えとなります。baa
などはa
が 2 回現れるため当てはまらないことに注意してください。
入力例 3
5 abcab
出力例 3
17
Score : 200 points
Problem Statement
You are given a string S of length N. Among its subsequences, count the ones such that all characters are different, modulo 10^9+7. Two subsequences are considered different if their characters come from different positions in the string, even if they are the same as strings.
Here, a subsequence of a string is a concatenation of one or more characters from the string without changing the order.
Constraints
- 1 \leq N \leq 100000
- S consists of lowercase English letters.
- |S|=N
Input
Input is given from Standard Input in the following format:
N S
Output
Print the number of the subsequences such that all characters are different, modulo 10^9+7.
Sample Input 1
4 abcd
Sample Output 1
15
Since all characters in S itself are different, all its subsequences satisfy the condition.
Sample Input 2
3 baa
Sample Output 2
5
The answer is five: b
, two occurrences of a
, two occurrences of ba
. Note that we do not count baa
, since it contains two a
s.
Sample Input 3
5 abcab
Sample Output 3
17
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
N 個の石が一列に並んでいて、左から i 個目の石は色 C_i で塗られています。
すぬけ君は、以下の操作を 0 回以上の任意の回数行います。
- 同じ色で塗られている 2 つの石を選ぶ。それらの石の間に置かれている石をすべて、選んだ石と同じ色で塗りかえる。
最終的な石の色の列としてありうるものの個数を 10^9+7 で割ったあまりを求めてください。
制約
- 1 \leq N \leq 2\times 10^5
- 1 \leq C_i \leq 2\times 10^5(1\leq i\leq N)
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N C_1 : C_N
出力
最終的な石の色の列としてありうるものの個数を 10^9+7 で割ったあまりを出力せよ。
入力例 1
5 1 2 1 2 2
出力例 1
3
以下の 3 通りの石の色の列を作ることができます。
- 操作を行わないことで、(1,2,1,2,2)
- 1,3 番目の石を選んで操作を行うことで、(1,1,1,2,2)
- 2,4 番目の石を選んで操作を行うことで、(1,2,2,2,2)
入力例 2
6 4 2 5 4 2 4
出力例 2
5
入力例 3
7 1 3 1 2 3 3 2
出力例 3
5
Score : 700 points
Problem Statement
There are N stones arranged in a row. The i-th stone from the left is painted in the color C_i.
Snuke will perform the following operation zero or more times:
- Choose two stones painted in the same color. Repaint all the stones between them, with the color of the chosen stones.
Find the number of possible final sequences of colors of the stones, modulo 10^9+7.
Constraints
- 1 \leq N \leq 2\times 10^5
- 1 \leq C_i \leq 2\times 10^5(1\leq i\leq N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N C_1 : C_N
Output
Print the number of possible final sequences of colors of the stones, modulo 10^9+7.
Sample Input 1
5 1 2 1 2 2
Sample Output 1
3
We can make three sequences of colors of stones, as follows:
- (1,2,1,2,2), by doing nothing.
- (1,1,1,2,2), by choosing the first and third stones to perform the operation.
- (1,2,2,2,2), by choosing the second and fourth stones to perform the operation.
Sample Input 2
6 4 2 5 4 2 4
Sample Output 2
5
Sample Input 3
7 1 3 1 2 3 3 2
Sample Output 3
5
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
整数 N,\ A,\ B が与えられます。 (0,\ 1,\ ...\ 2^N-1) の順列 (P_0,\ P_1,\ ...\ P_{2^N-1}) であって、 次の条件をすべて満たすものが存在するかどうか判定してください。 また、存在するなら 1 つ構成してください。
- P_0=A
- P_{2^N-1}=B
- すべての 0 \leq i < 2^N-1 について、P_i と P_{i+1} は 2 進数表記でちょうど 1 桁だけ異なる。
制約
- 1 \leq N \leq 17
- 0 \leq A \leq 2^N-1
- 0 \leq B \leq 2^N-1
- A \neq B
- 入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A B
出力
条件を満たす順列が存在しないならば NO
と出力せよ。
存在するならば、まず 1 行目に YES
と出力せよ。
そして 2 行目に (P_0,\ P_1,\ ...\ P_{2^N-1}) を空白区切りで出力せよ。
なお、解が複数個存在する場合はどれを出力してもよい。
入力例 1
2 1 3
出力例 1
YES 1 0 2 3
P=(1,0,2,3) を 2 進数表記すると (01,00,10,11) となり、どの隣り合う 2 要素もちょうど 1 桁だけ異なります。
入力例 2
3 2 1
出力例 2
NO
Score : 800 points
Problem Statement
You are given integers N,\ A and B. Determine if there exists a permutation (P_0,\ P_1,\ ...\ P_{2^N-1}) of (0,\ 1,\ ...\ 2^N-1) that satisfies all of the following conditions, and create one such permutation if it exists.
- P_0=A
- P_{2^N-1}=B
- For all 0 \leq i < 2^N-1, the binary representations of P_i and P_{i+1} differ by exactly one bit.
Constraints
- 1 \leq N \leq 17
- 0 \leq A \leq 2^N-1
- 0 \leq B \leq 2^N-1
- A \neq B
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A B
Output
If there is no permutation that satisfies the conditions, print NO
.
If there is such a permutation, print YES
in the first line.
Then, print (P_0,\ P_1,\ ...\ P_{2^N-1}) in the second line, with spaces in between.
If there are multiple solutions, any of them is accepted.
Sample Input 1
2 1 3
Sample Output 1
YES 1 0 2 3
The binary representation of P=(1,0,2,3) is (01,00,10,11), where any two adjacent elements differ by exactly one bit.
Sample Input 2
3 2 1
Sample Output 2
NO
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
1 から N の整数からなる 2 つの順列 p と q に対して、順列 f(p,q) を以下を満たす順列として定めます。
- f(p,q) の p_i (1 \leq i \leq N) 項目の値は q_i である。 ただし, p_i, q_i はそれぞれ p, q の i 項目の値を表している。
1 から N の整数からなる 2 つの順列 p, q が与えられます。 このとき、1 から N の順列からなる列 {a_n} を以下のように定めます。
- a_1=p, a_2=q
- a_{n+2}=f(a_n,a_{n+1}) ( n \geq 1 )
正整数 K が与えられるので、a_K を求めて下さい。
制約
- 1 \leq N \leq 10^5
- 1 \leq K \leq 10^9
- p と q は 1 から N の順列である。
入力
入力は以下の形式で標準入力から与えられる。
N K p_1 ... p_N q_1 ... q_N
出力
N 個の整数を空白区切りで出力せよ。 i (1 \leq i \leq N) 番目には a_K の i 項目の値を出力せよ。
入力例 1
3 3 1 2 3 3 2 1
出力例 1
3 2 1
a_3=f(p,q) であるから、f(p,q) が求められればよいです。 この場合は p_i=i なので、f(p,q)=q となります。
入力例 2
5 5 4 5 1 2 3 3 2 1 5 4
出力例 2
4 3 2 1 5
入力例 3
10 1000000000 7 10 6 5 4 2 9 1 3 8 4 1 9 2 3 7 8 10 6 5
出力例 3
7 9 4 8 2 5 1 6 10 3
Score : 1000 points
Problem Statement
For two permutations p and q of the integers from 1 through N, let f(p,q) be the permutation that satisfies the following:
- The p_i-th element (1 \leq i \leq N) in f(p,q) is q_i. Here, p_i and q_i respectively denote the i-th element in p and q.
You are given two permutations p and q of the integers from 1 through N. We will now define a sequence {a_n} of permutations of the integers from 1 through N, as follows:
- a_1=p, a_2=q
- a_{n+2}=f(a_n,a_{n+1}) ( n \geq 1 )
Given a positive integer K, find a_K.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq K \leq 10^9
- p and q are permutations of the integers from 1 through N.
Input
Input is given from Standard Input in the following format:
N K p_1 ... p_N q_1 ... q_N
Output
Print N integers, with spaces in between. The i-th integer (1 \leq i \leq N) should be the i-th element in a_K.
Sample Input 1
3 3 1 2 3 3 2 1
Sample Output 1
3 2 1
Since a_3=f(p,q), we just need to find f(p,q). We have p_i=i here, so f(p,q)=q.
Sample Input 2
5 5 4 5 1 2 3 3 2 1 5 4
Sample Output 2
4 3 2 1 5
Sample Input 3
10 1000000000 7 10 6 5 4 2 9 1 3 8 4 1 9 2 3 7 8 10 6 5
Sample Output 3
7 9 4 8 2 5 1 6 10 3
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 1300 点
問題文
とある博物館には宝石 1, 2, ..., N が展示されています。 宝石 i の置いてある場所は (x_i, y_i) で、価値は v_i です (この博物館は二次元平面として解釈できます)。
怪盗すぬけはいくつか宝石を盗みます。
宝石の盗み方には条件 1, 2, ..., M があり、すべて満たさないと探偵に捕まってしまいます。 条件はそれぞれ以下の4種類のいずれかです。
- (t_i =
L
, a_i, b_i) : 盗んだ宝石のうち、x 座標が a_i 以下の宝石が b_i 個以下 - (t_i =
R
, a_i, b_i) : 盗んだ宝石のうち、x 座標が a_i 以上の宝石が b_i 個以下 - (t_i =
D
, a_i, b_i) : 盗んだ宝石のうち、y 座標が a_i 以下の宝石が b_i 個以下 - (t_i =
U
, a_i, b_i) : 盗んだ宝石のうち、y 座標が a_i 以上の宝石が b_i 個以下
怪盗すぬけが盗める宝石の価値の総和の最大値を求めてください。
制約
- 1 \leq N \leq 80
- 1 \leq x_i, y_i \leq 100
- 1 \leq v_i \leq 10^{15}
- 1 \leq M \leq 320
- t_i は
L
,R
,U
,D
のいずれか - 1 \leq a_i \leq 100
- 0 \leq b_i \leq N - 1
- (x_i, y_i) は互いに相違なる
- (t_i, a_i) は互いに相違なる
- (t_i, b_i) は互いに相違なる
入力
入力は以下の形式で標準入力から与えられる。
N x_1 y_1 v_1 x_2 y_2 v_2 : x_N y_N v_N M t_1 a_1 b_1 t_2 a_2 b_2 : t_M a_M b_M
出力
怪盗すぬけが盗める宝石の価値の総和の最大値を出力せよ。
入力例 1
7 1 3 6 1 5 9 3 1 8 4 3 8 6 2 9 5 4 11 5 7 10 4 L 3 1 R 2 3 D 5 3 U 4 2
出力例 1
36
宝石 1, 5, 6, 7 を盗むと価値の総和が 36 となります。
入力例 2
3 1 2 3 4 5 6 7 8 9 1 L 100 0
出力例 2
0
入力例 3
4 1 1 10 1 2 11 2 1 12 2 2 13 3 L 8 3 L 9 2 L 10 1
出力例 3
13
入力例 4
10 66 47 71040136000 65 77 74799603000 80 53 91192869000 24 34 24931901000 91 78 49867703000 68 71 46108236000 46 73 74799603000 56 63 93122668000 32 51 71030136000 51 26 70912345000 21 L 51 1 L 7 0 U 47 4 R 92 0 R 91 1 D 53 2 R 65 3 D 13 0 U 63 3 L 68 3 D 47 1 L 91 5 R 32 4 L 66 2 L 80 4 D 77 4 U 73 1 D 78 5 U 26 5 R 80 2 R 24 5
出力例 4
305223377000
Score : 1300 points
Problem Statement
A museum exhibits N jewels, Jewel 1, 2, ..., N. The coordinates of Jewel i are (x_i, y_i) (the museum can be regarded as a two-dimensional plane), and the value of that jewel is v_i.
Snuke the thief will steal some of these jewels.
There are M conditions, Condition 1, 2, ..., M, that must be met when stealing jewels, or he will be caught by the detective. Each condition has one of the following four forms:
- (t_i =
L
, a_i, b_i) : Snuke can only steal at most b_i jewels whose x coordinates are a_i or smaller. - (t_i =
R
, a_i, b_i) : Snuke can only steal at most b_i jewels whose x coordinates are a_i or larger. - (t_i =
D
, a_i, b_i) : Snuke can only steal at most b_i jewels whose y coordinates are a_i or smaller. - (t_i =
U
, a_i, b_i) : Snuke can only steal at most b_i jewels whose y coordinates are a_i or larger.
Find the maximum sum of values of jewels that Snuke the thief can steal.
Constraints
- 1 \leq N \leq 80
- 1 \leq x_i, y_i \leq 100
- 1 \leq v_i \leq 10^{15}
- 1 \leq M \leq 320
- t_i is
L
,R
,U
orD
. - 1 \leq a_i \leq 100
- 0 \leq b_i \leq N - 1
- (x_i, y_i) are pairwise distinct.
- (t_i, a_i) are pairwise distinct.
- (t_i, b_i) are pairwise distinct.
Input
Input is given from Standard Input in the following format:
N x_1 y_1 v_1 x_2 y_2 v_2 : x_N y_N v_N M t_1 a_1 b_1 t_2 a_2 b_2 : t_M a_M b_M
Output
Print the maximum sum of values of jewels that Snuke the thief can steal.
Sample Input 1
7 1 3 6 1 5 9 3 1 8 4 3 8 6 2 9 5 4 11 5 7 10 4 L 3 1 R 2 3 D 5 3 U 4 2
Sample Output 1
36
Stealing Jewel 1, 5, 6 and 7 results in the total value of 36.
Sample Input 2
3 1 2 3 4 5 6 7 8 9 1 L 100 0
Sample Output 2
0
Sample Input 3
4 1 1 10 1 2 11 2 1 12 2 2 13 3 L 8 3 L 9 2 L 10 1
Sample Output 3
13
Sample Input 4
10 66 47 71040136000 65 77 74799603000 80 53 91192869000 24 34 24931901000 91 78 49867703000 68 71 46108236000 46 73 74799603000 56 63 93122668000 32 51 71030136000 51 26 70912345000 21 L 51 1 L 7 0 U 47 4 R 92 0 R 91 1 D 53 2 R 65 3 D 13 0 U 63 3 L 68 3 D 47 1 L 91 5 R 32 4 L 66 2 L 80 4 D 77 4 U 73 1 D 78 5 U 26 5 R 80 2 R 24 5
Sample Output 4
305223377000
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 2000 点
問題文
N 頂点 M 辺の連結なグラフが与えられます.各頂点には 1, 2,...,N と番号がついています. i(1 \leq i \leq M) 番目の辺は頂点 A_i と頂点 B_i を繋ぐ長さ C_i の無向辺です. また,奇数 MOD が与えられます.
Q 個のクエリが与えられるので,処理してください.クエリの形式は以下の通りです.
- i 番目のクエリでは,S_i,T_i,R_i が与えられる.頂点 S_i から頂点 T_i へ至る経路であって,長さを MOD で割った余りが R_i になるようなものが存在する場合は
YES
を,存在しない場合はNO
を出力する.ただし同じ辺を複数回通っても,来た辺をすぐ戻ってもよい.
ただし,この問題においての経路の長さは辺の長さの単純な和ではなく,1 本目に使う辺の長さを 1 倍,2 本目に使う辺の長さを 2 倍,3 本目に使う辺の長さを 4 倍,... したものの和とします. (より厳密には,長さ L_1,...,L_k の辺をこの順に使ったとすると,その経路の長さは L_i \times 2^{i-1} の和です.)
制約
- 1 \leq N,M,Q \leq 50000
- 3 \leq MOD \leq 10^{6}
- MOD は奇数
- 1 \leq A_i,B_i\leq N
- 0 \leq C_i \leq MOD-1
- 1 \leq S_i,T_i \leq N
- 0 \leq R_i \leq MOD-1
- 与えられるグラフは連結 (ただし自己辺や多重辺を含むことがある)
入力
入力は以下の形式で標準入力から与えられる.
N M Q MOD A_1 B_1 C_1 \vdots A_M B_M C_M S_1 T_1 R_1 \vdots S_Q T_Q R_Q
出力
i 行目に,i 番目のクエリに対する答えを出力せよ.
入力例 1
3 2 2 2019 1 2 1 2 3 2 1 3 5 1 3 4
出力例 1
YES NO
各クエリに対する答えは以下のようになります.
- 1 番目のクエリ: 頂点 1,2,3 の順に進むと経路の長さは 1 \times 2^0 + 2 \times 2^1 = 5 となり,長さを 2019 で割った余りが 5 になる経路は存在するので,答えは
YES
である. - 2 番目のクエリ: どのように頂点 1 から頂点 3 まで進んでも経路の長さを 2019 で割った余りが 4 となることはないので,答えは
NO
である.
入力例 2
6 6 3 2019 1 2 4 2 3 4 3 4 4 4 5 4 5 6 4 6 1 4 2 6 1110 3 1 1111 4 5 1112
出力例 2
YES NO NO
入力例 3
1 2 3 25 1 1 1 1 1 2 1 1 13 1 1 6 1 1 14
出力例 3
YES YES YES
入力例 4
10 15 10 15 1 2 1 2 3 6 3 4 6 2 5 1 5 6 1 4 7 6 1 8 11 2 9 6 5 10 11 9 10 11 3 6 1 2 5 1 2 7 11 9 10 11 5 6 11 1 3 5 9 8 3 7 7 7 7 10 13 4 1 10 9 3 12 10 10 14 9 2 1 6 6 5 8 8 4
出力例 4
YES NO NO NO NO NO NO YES YES NO
Score : 2000 points
Problem Statement
You are given a connected graph with N vertices and M edges. The vertices are numbered 1 to N. The i-th edge is an undirected edge of length C_i connecting Vertex A_i and Vertex B_i.
Additionally, an odd number MOD is given.
You will be given Q queries, which should be processed. The queries take the following form:
- Given in the i-th query are S_i, T_i and R_i. Print
YES
if there exists a path from Vertex S_i to Vertex T_i whose length is R_i modulo MOD, and printNO
otherwise. A path may traverse the same edge multiple times, or go back using the edge it just used.
Here, in this problem, the length of a path is NOT the sum of the lengths of its edges themselves, but the length of the first edge used in the path gets multiplied by 1, the second edge gets multiplied by 2, the third edge gets multiplied by 4, and so on. (More formally, let L_1,...,L_k be the lengths of the edges used, in this order. The length of that path is the sum of L_i \times 2^{i-1}.)
Constraints
- 1 \leq N,M,Q \leq 50000
- 3 \leq MOD \leq 10^{6}
- MOD is odd.
- 1 \leq A_i,B_i\leq N
- 0 \leq C_i \leq MOD-1
- 1 \leq S_i,T_i \leq N
- 0 \leq R_i \leq MOD-1
- The given graph is connected. (It may contain self-loops or multiple edges.)
Input
Input is given from Standard Input in the following format:
N M Q MOD A_1 B_1 C_1 \vdots A_M B_M C_M S_1 T_1 R_1 \vdots S_Q T_Q R_Q
Output
Print the answers to the i-th query in the i-th line.
Sample Input 1
3 2 2 2019 1 2 1 2 3 2 1 3 5 1 3 4
Sample Output 1
YES NO
The answer to each query is as follows:
- The first query: If we take the path 1,2,3, its length is 1 \times 2^0 + 2 \times 2^1 = 5, so there exists a path whose length is 5 modulo 2019. The answer is
YES
. - The second query: No matter what path we take from Vertex 1 to Vertex 3, its length will never be 4 modulo 2019. The answer is
NO
.
Sample Input 2
6 6 3 2019 1 2 4 2 3 4 3 4 4 4 5 4 5 6 4 6 1 4 2 6 1110 3 1 1111 4 5 1112
Sample Output 2
YES NO NO
Sample Input 3
1 2 3 25 1 1 1 1 1 2 1 1 13 1 1 6 1 1 14
Sample Output 3
YES YES YES
Sample Input 4
10 15 10 15 1 2 1 2 3 6 3 4 6 2 5 1 5 6 1 4 7 6 1 8 11 2 9 6 5 10 11 9 10 11 3 6 1 2 5 1 2 7 11 9 10 11 5 6 11 1 3 5 9 8 3 7 7 7 7 10 13 4 1 10 9 3 12 10 10 14 9 2 1 6 6 5 8 8 4
Sample Output 4
YES NO NO NO NO NO NO YES YES NO