Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
正整数 N が与えられます。 N の正の奇数の約数と正の偶数の約数はどちらが多いか答えてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 入力は全て整数
- 1 \leq T \leq 2 \times 10^5
- 1 \leq N \leq 10^{18}
入力
入力は以下の形式で標準入力から与えられる。
T case_1 \vdots case_T
各ケースは以下の形式で与えられる。
N
出力
T 行出力せよ。 i 行目には case_i に対応する答えを出力せよ。各ケースでは、正の奇数の約数の方が多ければ Odd と、正の偶数の約数の方が多ければ Even と、同数であれば Same と出力せよ。
入力例 1
3 2 998244353 1000000000000000000
出力例 1
Same Odd Even
2 は 1 つの正の奇数の約数と、 1 つの正の偶数の約数を持ちます。
Score : 300 points
Problem Statement
Given is a positive integer N. Which are there more of, positive odd divisors of N or positive even divisors of N?
You will be given T test cases. Solve each of them.
Constraints
- All values in input are integers.
- 1 \leq T \leq 2 \times 10^5
- 1 \leq N \leq 10^{18}
Input
Input is given from Standard Input in the following format:
T case_1 \vdots case_T
Each case is in the following format:
N
Constraints
Print T lines. The i-th line should contain the answer to case_i: Odd if there are more positive odd divisors, Even if there are more positive even divisors, and Same if there are the same number of odd and even divisors.
Sample Input 1
3 2 998244353 1000000000000000000
Sample Output 1
Same Odd Even
2 has one positive odd divisor and one positive even divisor.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
長さ N の整数列 A が与えられます。A の空でない部分列 B は 2^N - 1 個あります。これらについて \max\left(B\right) \times \min\left(B\right) の値を計算し、その総和を答えてください。
ただし、答えは非常に大きくなる場合があるので、 998244353 で割った余りを答えてください。
制約
- 入力は全て整数
- 1 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 998244352
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \cdots A_N
出力
答えを出力せよ。
入力例 1
3 2 4 3
出力例 1
63
B として、以下の 7 つが考えられます。
- B = \left(2\right) : \max\left(B\right) \times \min\left(B\right) = 4
- B = \left(4\right) : \max\left(B\right) \times \min\left(B\right) = 16
- B = \left(3\right) : \max\left(B\right) \times \min\left(B\right) = 9
- B = \left(2, 4\right) : \max\left(B\right) \times \min\left(B\right) = 8
- B = \left(2, 3\right) : \max\left(B\right) \times \min\left(B\right) = 6
- B = \left(4, 3\right) : \max\left(B\right) \times \min\left(B\right) = 12
- B = \left(2, 4, 3\right) : \max\left(B\right) \times \min\left(B\right) = 8
以上の 7 つの値を足した値 63 が答えです。
入力例 2
1 10
出力例 2
100
入力例 3
7 853983 14095 543053 143209 4324 524361 45154
出力例 3
206521341
Score : 400 points
Problem Statement
Given is a sequence A of N integers. There are 2^N - 1 non-empty subsequences B of A. Find the sum of \max\left(B\right) \times \min\left(B\right) over all of them.
Since the answer can be enormous, report it modulo 998244353.
Constraints
- All values in input are integers.
- 1 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 998244352
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
Print the answer.
Sample Input 1
3 2 4 3
Sample Output 1
63
There are 7 subsequences B, as follows:
- B = \left(2\right) : \max\left(B\right) \times \min\left(B\right) = 4
- B = \left(4\right) : \max\left(B\right) \times \min\left(B\right) = 16
- B = \left(3\right) : \max\left(B\right) \times \min\left(B\right) = 9
- B = \left(2, 4\right) : \max\left(B\right) \times \min\left(B\right) = 8
- B = \left(2, 3\right) : \max\left(B\right) \times \min\left(B\right) = 6
- B = \left(4, 3\right) : \max\left(B\right) \times \min\left(B\right) = 12
- B = \left(2, 4, 3\right) : \max\left(B\right) \times \min\left(B\right) = 8
The answer is the sum of them: 63.
Sample Input 2
1 10
Sample Output 2
100
Sample Input 3
7 853983 14095 543053 143209 4324 524361 45154
Sample Output 3
206521341
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
整数 N , M が与えられます。 長さ N の整数列 A であって、以下の条件を満たすものの数を答えてください。
- 1 \leq A_i \leq M \left(i = 1, 2, \ldots, N\right)
- A_{i+1} は A_i の倍数 \left(i = 1, 2, \ldots, N - 1\right)
ただし、答えは非常に大きくなる場合があるので、 998244353 で割った余りを答えてください。
制約
- 入力は全て整数
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを出力せよ。
入力例 1
3 4
出力例 1
13
条件を満たす数列 A として、例えば以下のようなものが考えられます。
- A = \left(1, 1, 4\right)
- A = \left(3, 3, 3\right)
- A = \left(1, 2, 4\right)
入力例 2
20 30
出力例 2
71166
入力例 3
200000 200000
出力例 3
835917264
Score : 500 points
Problem Statement
Given are integers N and M. How many sequences A of N integers satisfy the following conditions?
- 1 \leq A_i \leq M \left(i = 1, 2, \ldots, N\right)
- A_{i+1} is a multiple of A_i. \left(i = 1, 2, \ldots, N - 1\right)
Since the answer can be enormous, report it modulo 998244353.
Constraints
- All values in input are integers.
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
Input
Input is given from Standard Input in the following format:
N M
Output
Print the answer.
Sample Input 1
3 4
Sample Output 1
13
Some of the sequences A satisfying the conditions follow:
- A = \left(1, 1, 4\right)
- A = \left(3, 3, 3\right)
- A = \left(1, 2, 4\right)
Sample Input 2
20 30
Sample Output 2
71166
Sample Input 3
200000 200000
Sample Output 3
835917264
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
整数 N , M が与えられます。 長さ N の整数列 A であって、以下の条件を満たすものの数を答えてください。
- 0 \leq A_i \left(i = 1, 2, \ldots, N\right)
- \sum_{i = 1}^{N} A_i = M
- A_1 xor A_2 xor \cdots xor A_N = 0 （ここで xor はビットごとの排他的論理和を表す）
ただし、答えは非常に大きくなる場合があるので、 998244353 で割った余りを答えてください。
制約
- 入力は全て整数
- 1 \leq N \leq 5000
- 1 \leq M \leq 5000
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを出力せよ。
入力例 1
5 20
出力例 1
475
条件を満たす数列 A として、例えば以下のようなものが考えられます。
- A = \left(10, 0, 10, 0, 0\right)
- A = \left(1, 2, 3, 7, 7\right)
入力例 2
10 5
出力例 2
0
入力例 3
3141 2718
出力例 3
371899128
Score : 500 points
Problem Statement
Given are integers N and M. How many sequences A of N integers satisfy the following conditions?
- 0 \leq A_i \left(i = 1, 2, \ldots, N\right)
- \sum_{i = 1}^{N} A_i = M
- A_1 xor A_2 xor \cdots xor A_N = 0 ("xor" denotes the bitwise XOR.)
Since the answer can be enormous, report it modulo 998244353.
Constraints
- All values in input are integers.
- 1 \leq N \leq 5000
- 1 \leq M \leq 5000
Input
Input is given from Standard Input in the following format:
N M
Output
Print the answer.
Sample Input 1
5 20
Sample Output 1
475
Some of the sequences A satisfying the conditions follow:
- A = \left(10, 0, 10, 0, 0\right)
- A = \left(1, 2, 3, 7, 7\right)
Sample Input 2
10 5
Sample Output 2
0
Sample Input 3
3141 2718
Sample Output 3
371899128
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
高橋国には N 箇所の町があり、それぞれ町 1 、町 2、 \ldots 、町 N と名付けられています。 この国には N-1 本の道があり、 i 本目の道は 町 u_i と町 v_i を双方向に結びます。任意の 2 つの町 a, b について、いくつかの道を通ることにより、町 a から町 b へ移動することが出来ます。
高橋国王は、ある情報を国土全体に流そうとしています。多忙な高橋国王は、 K 箇所までの町にしか直接情報を伝達することが出来ません。
高橋国王の情報伝達が終わった瞬間を時刻 0 とします。 t = 1, 2, 3, \cdots について、以下の現象が発生します。
- 1 本の道で直接結ばれている町の組 a, b について、 時刻 t-0.5 に町 a に情報が伝わっており、町 b に情報が伝わっていないとき、 時刻 t に町 b にも情報が伝わる。
高橋国王は K 箇所の連絡先を適切に選択し、全ての町に情報が伝わるまでに掛かる時間を最小化しようと考えています。最小値を答えてください。
制約
- 入力は全て整数
- 1 \leq K < N \leq 2 \times 10^5
- 1 \leq u_i, v_i \leq N
- 任意の 2 つの町 a, b について、いくつかの道を通ることにより、町 a から町 b へ移動することが出来る。
入力
入力は以下の形式で標準入力から与えられる。
N K
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
出力
答えを出力せよ。
入力例 1
5 2 1 2 2 3 3 4 4 5
出力例 1
1
高橋国王が町 2 と町 4 に直接情報を伝達した場合、町 1 、 \ldots 、町5 に初めて情報が伝わる時刻は、それぞれ 1, 0, 1, 0, 1 となります。このとき、 国土全体に情報が広まるのは時刻 1 であり、これが達成可能な最小値であることが証明出来ます。
入力例 2
5 1 1 2 1 3 1 4 5 4
出力例 2
2
入力例 3
20 3 2 15 6 5 12 1 7 9 17 2 15 5 2 4 17 16 12 2 8 17 17 19 18 11 20 8 20 3 13 9 11 10 11 20 14 8 11 7
出力例 3
3
Score : 800 points
Problem Statement
Takahashi Kingdom has N towns, called Town 1 through N. There are N-1 roads in this kingdom. The i-th road connects Town u_i and Town v_i bidirectionally. For any two towns a and b, it is possible to get from Town a to Town b by traversing some roads.
Takahashi, the king, wants to spread some information all over the kingdom. Since he is busy, he can directly transmit this information to at most K towns.
Assume that Takahashi finishes transmitting the information at time 0. Then, for each t = 1, 2, 3, \cdots, the following happens:
- For towns a and b directly connected by a road, if a has already received the information at time t - 0.5 but b has not, b receives it at time t.
Takahashi wants to choose the K towns to transmit the information to minimize the time taken until every town receives it. Find the minimum time this takes.
Constraints
- All values in input are integers.
- 1 \leq K < N \leq 2 \times 10^5
- 1 \leq u_i, v_i \leq N
- For any two towns a and b, it is possible to get from Town a to Town b by traversing some roads.
Input
Input is given from Standard Input in the following format:
N K
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
Output
Print the answer.
Sample Input 1
5 2 1 2 2 3 3 4 4 5
Sample Output 1
1
If Takahashi directly transmits the information to Town 2 and 4, Town 1, 2, 3, 4, 5 receives it at time 1, 0, 1, 0, 1, respectively. In this case, the information is spread all over the kingdom at time 1. We can prove that this is the earliest possible time.
Sample Input 2
5 1 1 2 1 3 1 4 5 4
Sample Output 2
2
Sample Input 3
20 3 2 15 6 5 12 1 7 9 17 2 15 5 2 4 17 16 12 2 8 17 17 19 18 11 20 8 20 3 13 9 11 10 11 20 14 8 11 7
Sample Output 3
3
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
K 個の数列が与えられます。 i 個目の数列 A_i の長さは N_i です。
これらを使って高橋君と青木君がゲームをします。 全ての数列が長さ 1 になるまで、高橋君と青木君が交互に以下の操作を行います。
- 長さが 2 以上の数列を 1 つ選び、その最初の要素或いは最後の要素を削除する。
高橋君が先に操作を行います。最後に残る K 個の要素の総和を、高橋君は最大化したいと、青木君は最小化したいと考えています。
両者最適に行動するとき、最後に残る K 個の要素の総和を答えてください。
制約
- 入力は全て整数
- 1 \leq K \leq 2 \times 10^5
- 1 \leq N_i
- \sum_i N_i \leq 2 \times 10^5
- 1 \leq A_{i, j} \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
K
N_1 A_{1, 1} A_{1, 2} \cdots A_{1, N_1}
N_2 A_{2, 1} A_{2, 2} \cdots A_{2, N_2}
\vdots
N_K A_{K, 1} A_{K, 2} \cdots A_{K, N_K}
出力
答えを出力せよ。
入力例 1
2 3 1 2 3 2 1 10
出力例 1
12
ゲームの進行の一例を示します。
- 高橋君が A_2 の最初の要素を削除する。現在の数列の状態は、 A_1 = \left(1, 2, 3\right), A_2 = \left(10\right) である。
- 青木君が A_1 の最後の要素を削除する。現在の数列の状態は、 A_1 = \left(1, 2\right), A_2 = \left(10\right) である。
- 高橋君が A_1 の最初の要素を削除する。現在の数列の状態は、 A_1 = \left(2\right), A_2 = \left(10\right) である。全ての数列の長さが 1 となった為、ゲームが終了する。
このとき、最後に残る K 個の要素の総和は 12 です。尚、このゲームの進行が両者にとって最適な行動であるとは限りません。
入力例 2
8 1 2 2 1 2 3 1 2 1 4 1 1 1 2 5 1 1 2 2 1 6 2 2 2 2 1 1 7 1 2 1 1 2 2 2 8 2 2 2 1 1 1 1 2
出力例 2
12
Score : 800 points
Problem Statement
We have K sequences. The i-th sequence A_i has the length of N_i.
Takahashi and Aoki will play a game using these. They will alternately do the following operation until the length of every sequence becomes 1:
- Choose a sequence of length at least 2, and delete its first or last element.
Takahashi goes first. Takahashi wants to maximize the sum of the K elements remaining in the end, while Aoki wants to minimize it.
Find the sum of the K elements remaining in the end when both players play optimally.
Constraints
- All values in input are integers.
- 1 \leq K \leq 2 \times 10^5
- 1 \leq N_i
- \sum_i N_i \leq 2 \times 10^5
- 1 \leq A_{i, j} \leq 10^9
Input
Input is given from Standard Input in the following format:
K
N_1 A_{1, 1} A_{1, 2} \cdots A_{1, N_1}
N_2 A_{2, 1} A_{2, 2} \cdots A_{2, N_2}
\vdots
N_K A_{K, 1} A_{K, 2} \cdots A_{K, N_K}
Output
Print the answer.
Sample Input 1
2 3 1 2 3 2 1 10
Sample Output 1
12
Here is one possible progression of the game:
- Takahashi deletes the first element of A_2. Now we have A_1 = \left(1, 2, 3\right), A_2 = \left(10\right).
- Aoki deletes the last element of A_1. Now we have A_1 = \left(1, 2\right), A_2 = \left(10\right).
- Takahashi deletes the first element of A_1. Now we have A_1 = \left(2\right), A_2 = \left(10\right). The length of every sequence has become 1, so the game ends.
In this case, the sum of the K elements remaining in the end is 12. Note that the players may have made suboptimal moves here.
Sample Input 2
8 1 2 2 1 2 3 1 2 1 4 1 1 1 2 5 1 1 2 2 1 6 2 2 2 2 1 1 7 1 2 1 1 2 2 2 8 2 2 2 1 1 1 1 2
Sample Output 2
12