Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
整数 N,K が与えられます。N 以下の正の整数の組 (a,b,c) であって、a+b,b+c,c+a がすべて K の倍数であるようなものの個数を求めてください。 ただし、a,b,c の順番を入れ替えただけの組も異なるものとして数えます。また、a,b,c の中に同じものがあっても構いません。
制約
- 1 \leq N,K \leq 2\times 10^5
- N,K は整数である
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
N 以下の正の整数の組 (a,b,c) であって、a+b,b+c,c+a がすべて K の倍数であるようなものの個数を出力せよ。
入力例 1
3 2
出力例 1
9
(1,1,1),(1,1,3),(1,3,1),(1,3,3),(2,2,2),(3,1,1),(3,1,3),(3,3,1),(3,3,3) が条件を満たします。
入力例 2
5 3
出力例 2
1
入力例 3
31415 9265
出力例 3
27
入力例 4
35897 932
出力例 4
114191
Score : 300 points
Problem Statement
You are given integers N and K. Find the number of triples (a,b,c) of positive integers not greater than N such that a+b,b+c and c+a are all multiples of K. The order of a,b,c does matter, and some of them can be the same.
Constraints
- 1 \leq N,K \leq 2\times 10^5
- N and K are integers.
Input
Input is given from Standard Input in the following format:
N K
Output
Print the number of triples (a,b,c) of positive integers not greater than N such that a+b,b+c and c+a are all multiples of K.
Sample Input 1
3 2
Sample Output 1
9
(1,1,1),(1,1,3),(1,3,1),(1,3,3),(2,2,2),(3,1,1),(3,1,3),(3,3,1) and (3,3,3) satisfy the condition.
Sample Input 2
5 3
Sample Output 2
1
Sample Input 3
31415 9265
Sample Output 3
27
Sample Input 4
35897 932
Sample Output 4
114191
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
整数 L が与えられます。以下の条件を満たす有向グラフをひとつ構成してください。構成したグラフに多重辺が含まれていても構いません。 なお、条件を満たす有向グラフは必ず存在することが証明できます。
- 頂点数 N は 20 以下で、すべての頂点には 1 以上 N 以下の相異なる番号が付けられている
- 辺数 M は 60 以下で、すべての辺には 0 以上 10^6 以下の整数の長さが付けられている
- 全ての辺は番号の小さい方の頂点から大きい方の頂点に向かって向きづけられている。すなわち、1,2,...,N はこのグラフの頂点の番号を適当なトポロジカル順序で並べてできる列である
- 頂点 1 から頂点 N への異なるパスはちょうど L 個あり、それらの長さは 0 から L-1 までの相異なる整数である
ただし、パスの長さとは、そのパス上の辺の長さの和を表します。また、2 つのパスが異なるとは、パス上の辺の集合が異なることを指します。
制約
- 2 \leq L \leq 10^6
- L は整数である
入力
入力は以下の形式で標準入力から与えられる。
L
出力
1 行目には、構成したグラフの頂点数 N と辺数 M を出力せよ。 続く M 行のうちの i 行目には、3 つの整数 u_i,v_i,w_i を出力せよ。これらはそれぞれ、i 本目の辺の始点、i 本目の辺の終点、i 本目の辺の長さを表す。 解が複数考えられる場合、どれを出力してもよい。
入力例 1
4
出力例 1
8 10 1 2 0 2 3 0 3 4 0 1 5 0 2 6 0 3 7 0 4 8 0 5 6 1 6 7 1 7 8 1
出力例のグラフには 頂点 1 から N=8 への 4 本のパスがあり、
- パス 1 → 2 → 3 → 4 → 8 の長さは 0
- パス 1 → 2 → 3 → 7 → 8 の長さは 1
- パス 1 → 2 → 6 → 7 → 8 の長さは 2
- パス 1 → 5 → 6 → 7 → 8 の長さは 3
となります。これ以外にも、正答として認められる出力があります。
入力例 2
5
出力例 2
5 7 1 2 0 2 3 1 3 4 0 4 5 0 2 4 0 1 3 3 3 5 1
Score : 700 points
Problem Statement
You are given an integer L. Construct a directed graph that satisfies the conditions below. The graph may contain multiple edges between the same pair of vertices. It can be proved that such a graph always exists.
- The number of vertices, N, is at most 20. The vertices are given ID numbers from 1 to N.
- The number of edges, M, is at most 60. Each edge has an integer length between 0 and 10^6 (inclusive).
- Every edge is directed from the vertex with the smaller ID to the vertex with the larger ID. That is, 1,2,...,N is one possible topological order of the vertices.
- There are exactly L different paths from Vertex 1 to Vertex N. The lengths of these paths are all different, and they are integers between 0 and L-1.
Here, the length of a path is the sum of the lengths of the edges contained in that path, and two paths are considered different when the sets of the edges contained in those paths are different.
Constraints
- 2 \leq L \leq 10^6
- L is an integer.
Input
Input is given from Standard Input in the following format:
L
Output
In the first line, print N and M, the number of the vertices and edges in your graph. In the i-th of the following M lines, print three integers u_i,v_i and w_i, representing the starting vertex, the ending vertex and the length of the i-th edge. If there are multiple solutions, any of them will be accepted.
Sample Input 1
4
Sample Output 1
8 10 1 2 0 2 3 0 3 4 0 1 5 0 2 6 0 3 7 0 4 8 0 5 6 1 6 7 1 7 8 1
In the graph represented by the sample output, there are four paths from Vertex 1 to N=8:
- 1 → 2 → 3 → 4 → 8 with length 0
- 1 → 2 → 3 → 7 → 8 with length 1
- 1 → 2 → 6 → 7 → 8 with length 2
- 1 → 5 → 6 → 7 → 8 with length 3
There are other possible solutions.
Sample Input 2
5
Sample Output 2
5 7 1 2 0 2 3 1 3 4 0 4 5 0 2 4 0 1 3 3 3 5 1
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
高橋君は、互いに区別できない K 面サイコロを N 個振ります。なお、K 面サイコロとは、1 以上 K 以下のすべての整数の目の出る可能性のあるサイコロのことを指します。 各 i=2,3,...,2K に対し、以下の値を 998244353 で割ったあまりをそれぞれ求めてください。
- どの異なる 2 つのサイコロの出目の和も i にならないような出目の組の場合の数
なお、サイコロ同士は区別しないことに注意してください。したがって、2 つの出目の組が異なるとは、ある目 k が存在し、出目 k の個数が異なることを指します。
制約
- 1 \leq K \leq 2000
- 2 \leq N \leq 2000
- K,N は整数である
入力
入力は以下の形式で標準入力から与えられる。
K N
出力
2K-1 個の整数を出力せよ。t(1\leq t\leq 2K-1) 個目には、i=t+1 のときの答えを出力せよ。
入力例 1
3 3
出力例 1
7 7 4 7 7
- i=2 のとき、出目の組 (1,2,2),(1,2,3),(1,3,3),(2,2,2),(2,2,3),(2,3,3),(3,3,3) が条件を満たすので、このときの答えは 7 です。
- i=3 のとき、出目の組 (1,1,1),(1,1,3),(1,3,3),(2,2,2),(2,2,3),(2,3,3),(3,3,3) が条件を満たすので、このときの答えは 7 です。
- i=4 のとき、出目の組 (1,1,1),(1,1,2),(2,3,3),(3,3,3) が条件を満たすので、このときの答えは 4 です。
入力例 2
4 5
出力例 2
36 36 20 20 20 36 36
入力例 3
6 1000
出力例 3
149393349 149393349 668669001 668669001 4000002 4000002 4000002 668669001 668669001 149393349 149393349
Score : 700 points
Problem Statement
Takahashi throws N dice, each having K sides with all integers from 1 to K. The dice are NOT pairwise distinguishable. For each i=2,3,...,2K, find the following value modulo 998244353:
- The number of combinations of N sides shown by the dice such that the sum of no two different sides is i.
Note that the dice are NOT distinguishable, that is, two combinations are considered different when there exists an integer k such that the number of dice showing k is different in those two.
Constraints
- 1 \leq K \leq 2000
- 2 \leq N \leq 2000
- K and N are integers.
Input
Input is given from Standard Input in the following format:
K N
Output
Print 2K-1 integers. The t-th of them (1\leq t\leq 2K-1) should be the answer for i=t+1.
Sample Input 1
3 3
Sample Output 1
7 7 4 7 7
- For i=2, the combinations (1,2,2),(1,2,3),(1,3,3),(2,2,2),(2,2,3),(2,3,3),(3,3,3) satisfy the condition, so the answer is 7.
- For i=3, the combinations (1,1,1),(1,1,3),(1,3,3),(2,2,2),(2,2,3),(2,3,3),(3,3,3) satisfy the condition, so the answer is 7.
- For i=4, the combinations (1,1,1),(1,1,2),(2,3,3),(3,3,3) satisfy the condition, so the answer is 4.
Sample Input 2
4 5
Sample Output 2
36 36 20 20 20 36 36
Sample Input 3
6 1000
Sample Output 3
149393349 149393349 668669001 668669001 4000002 4000002 4000002 668669001 668669001 149393349 149393349
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1200 点
問題文
1,2,...,N の並び替え p_1,p_2,...,p_N が与えられます。以下の操作を好きなだけ繰り返してすべての i に対して p_i=i となるようにできるか判定してください。
- p_{i-1}>p_{i}>p_{i+1} なる 3 項組 (2\leq i\leq N-1) を選び、この 3 項を逆順に並び替える。
制約
- 3 \leq N \leq 3 × 10^5
- p_1,p_2,...,p_N は 1,2,...,N の並び替えである
入力
入力は以下の形式で標準入力から与えられる。
N p_1 : p_N
出力
操作を繰り返してすべての i に対して p_i=i となるようにできる場合は Yes を、そうでない場合は No を出力せよ。
入力例 1
5 5 2 1 4 3
出力例 1
Yes
以下の操作ですべての i に対して p_i=i となるようにできます。
- p_1,p_2,p_3 を逆順に並び替える。列 p は 1,2,5,4,3 となる。
- p_3,p_4,p_5 を逆順に並び替える。列 p は 1,2,3,4,5 となる。
入力例 2
4 3 2 4 1
出力例 2
No
入力例 3
7 3 2 1 6 5 4 7
出力例 3
Yes
入力例 4
6 5 3 4 1 2 6
出力例 4
No
Score : 1200 points
Problem Statement
You are given a permutation of 1,2,...,N: p_1,p_2,...,p_N. Determine if the state where p_i=i for every i can be reached by performing the following operation any number of times:
- Choose three elements p_{i-1},p_{i},p_{i+1} (2\leq i\leq N-1) such that p_{i-1}>p_{i}>p_{i+1} and reverse the order of these three.
Constraints
- 3 \leq N \leq 3 × 10^5
- p_1,p_2,...,p_N is a permutation of 1,2,...,N.
Input
Input is given from Standard Input in the following format:
N p_1 : p_N
Output
If the state where p_i=i for every i can be reached by performing the operation, print Yes; otherwise, print No.
Sample Input 1
5 5 2 1 4 3
Sample Output 1
Yes
The state where p_i=i for every i can be reached as follows:
- Reverse the order of p_1,p_2,p_3. The sequence p becomes 1,2,5,4,3.
- Reverse the order of p_3,p_4,p_5. The sequence p becomes 1,2,3,4,5.
Sample Input 2
4 3 2 4 1
Sample Output 2
No
Sample Input 3
7 3 2 1 6 5 4 7
Sample Output 3
Yes
Sample Input 4
6 5 3 4 1 2 6
Sample Output 4
No