Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
正整数 N, M があります。ここで N \lt M が成り立ちます。
Alice と Bob がゲームをします。2 人は 1, 2, \dots, N が書かれたカードを 1 枚ずつ、合計 N 枚のカードをそれぞれ持っています。
ゲームでは Alice を先攻として 2 人が交互に「手札を 1 枚選び、場に出す」という操作を繰り返します。
カードが場に出た直後に、今まで場に出たカードに書かれている数の総和が M で割り切れる状態になったら、直前にカードを出した人の負け、そうでない人の勝ちとなります。
上の条件を満たすことなく両者が持っているカードを全て出し切った場合は Alice の勝ちとなります。
双方が最適に行動した時、Alice と Bob のどちらが勝ちますか？
T 個のテストケースが与えられるので、それぞれに対して答えを求めてください。
制約
- 1 \leq T \leq 10^5
- 1 \leq N \lt M \leq 10^9
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。ここで \mathrm{case}_i は i 番目のテストケースを意味する。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる。
N M
出力
T 行出力せよ。i 行目には i 番目のテストケースへの答えを出力せよ。
各テストケースでは、双方が最適に行動した時に Alice が勝つ場合は Alice を、Bob が勝つ場合は Bob を出力せよ。
入力例 1
8 2 3 3 6 5 9 45 58 39 94 36 54 74 80 61 95
出力例 1
Alice Alice Bob Bob Alice Bob Bob Alice
1 番目のテストケースにおいて、ゲームの進行例を挙げると以下のようになります。
- はじめ、Alice と Bob はともに 1 が書かれたカードと 2 が書かれたカードの 2 枚を持っている。
- Alice が 1 が書かれたカードを出す。
- 今まで場に出たカードに書かれている数の総和は 1 であり、これは 3 で割り切れないので Alice の負けにはならない。
- Bob が 1 が書かれたカードを出す。
- 今まで場に出たカードに書かれている数の総和は 2 であり、これは 3 で割り切れないので Bob の負けにはならない。
- Alice が 2 が書かれたカードを出す。
- 今まで場に出たカードに書かれている数の総和は 4 であり、これは 3 で割り切れないので Alice の負けにはならない。
- Bob が 2 が書かれたカードを出す。
- 今まで場に出たカードに書かれている数の総和は 6 であり、これは 3 で割り切れるので、Bob の負け、Alice の勝ちとなる。
1 番目のテストケースでは、Bob がどのように行動しても Alice が勝つことが出来ます。
Score : 600 points
Problem Statement
There are positive integers N and M, where N \lt M.
Alice and Bob will play a game. Each player has N cards with 1, 2, \dots, N written on them, one for each number.
Starting with Alice, the two players take turns repeatedly performing this action: choose one card from their hand and play it onto the table.
Immediately after a card is played onto the table, if the sum of the numbers on the cards that have been played so far is divisible by M, the player who just played the card loses, and the other player wins.
If both players play all their cards without satisfying the above condition, Alice wins.
Who will win, Alice or Bob, when both play optimally?
You are given T test cases. Solve each of them.
Constraints
- 1 \leq T \leq 10^5
- 1 \leq N \lt M \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format. Here, \mathrm{case}_i denotes the i-th test case.
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N M
Output
Print T lines. The i-th line should contain the answer for the i-th test case.
For each test case, if Alice wins when both play optimally, print Alice; if Bob wins, print Bob.
Sample Input 1
8 2 3 3 6 5 9 45 58 39 94 36 54 74 80 61 95
Sample Output 1
Alice Alice Bob Bob Alice Bob Bob Alice
In the first test case, the game could proceed as follows.
- Initially, both Alice and Bob have two cards: the card with 1 and the card with 2.
- Alice plays the card with 1.
- The sum of the numbers on the cards played so far is 1, which is not divisible by 3, so Alice does not lose.
- Bob plays the card with 1.
- The sum is now 2, which is not divisible by 3, so Bob does not lose.
- Alice plays the card with 2.
- The sum is now 4, which is not divisible by 3, so Alice does not lose.
- Bob plays the card with 2.
- The sum is now 6, which is divisible by 3, so Bob loses and Alice wins.
In the first test case, no matter how Bob plays, Alice can win.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
長さ N の整数列 A = (A_1, A_2, \dots, A_N) があります。
あなたは次の操作を 0 回以上好きな回数行うことが出来ます。
- 1 \leq i \lt j \leq N を満たす整数対 (i, j) を選び、A_i を A_i + 1 に、A_j を A_j - 1 に置き換える。
操作によって A を広義単調増加な数列にすることが可能かどうか判定してください。
T 個のテストケースが与えられるので、それぞれに対して答えを求めてください。
制約
- 1 \leq T \leq 2 \times 10^5
- 2 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 10^9
- 全てのテストケースに対する N の総和は 2 \times 10^5 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。ここで \mathrm{case}_i は i 番目のテストケースを意味する。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる。
N A_1 A_2 \dots A_N
出力
T 行出力せよ。i 行目には i 番目のテストケースへの答えを出力せよ。
各テストケースでは、操作によって A を広義単調増加な数列にすることが可能な場合は Yes を、そうでない場合は No を出力せよ。
入力例 1
3 3 1 7 5 2 9 0 10 607 495 419 894 610 636 465 331 925 724
出力例 1
Yes No Yes
1 番目のテストケースでは、次のように操作を行うことで A を広義単調増加な数列にすることが出来ます。
- (i, j) として (1, 2) を選ぶ。操作後の A は (2, 6, 5) になる。
- (i, j) として (1, 2) を選ぶ。操作後の A は (3, 5, 5) になる。
2 番目のテストケースでは、どのように操作しても A を広義単調増加な数列にすることは出来ません。
Score : 600 points
Problem Statement
You are given an integer sequence A = (A_1, A_2, \dots, A_N) of length N.
You can perform the following operation any number of times, possibly zero:
- Choose an integer pair (i, j) satisfying 1 \leq i \lt j \leq N, and replace A_i with A_i + 1 and A_j with A_j - 1.
Determine whether it is possible to make A a non-decreasing sequence through the operations.
You are given T test cases. Solve each of them.
Constraints
- 1 \leq T \leq 2 \times 10^5
- 2 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 10^9
- The sum of N over all test cases is at most 2 \times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format. Here, \mathrm{case}_i denotes the i-th test case.
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N A_1 A_2 \dots A_N
Output
Print T lines. The i-th line should contain the answer for the i-th test case.
For each test case, if it is possible to make A a non-decreasing sequence through the operations, print Yes; otherwise, print No.
Sample Input 1
3 3 1 7 5 2 9 0 10 607 495 419 894 610 636 465 331 925 724
Sample Output 1
Yes No Yes
In the first test case, you can make A into a non-decreasing sequence by performing the following operations:
- Choose (i, j) = (1, 2). After the operation, A is (2, 6, 5).
- Choose (i, j) = (1, 2). After the operation, A is (3, 5, 5).
In the second test case, you cannot make A into a non-decreasing sequence no matter how you perform the operations.
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
整数列 A = (A_1, A_2, \dots, A_N) および整数 X が与えられます。
次の条件を全て満たす整数の組 (i, j, k) を 1 組出力してください。条件を満たす組が存在しない場合はそのことを報告してください。
- 1 \leq i \lt j \lt k \leq N
- A_i + A_j + A_k = X
制約
- 3 \leq N \leq 10^6
- 1 \leq X \leq 10^6
- 1 \leq A_i \leq X
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N X A_1 A_2 \dots A_N
出力
条件を満たす整数の組 (i, j, k) が存在する場合、以下の形式で出力せよ。答えが複数ある場合はどれを出力しても良い。
i j k
条件を満たす整数の組が存在しない場合、-1 を出力せよ。
入力例 1
5 16 1 8 5 10 13
出力例 1
1 3 4
(i, j, k) = (1, 3, 4) は 1 \leq i \lt j \lt k \leq N かつ A_i + A_j + A_k = 1 + 5 + 10 = 16 = X を満たします。
入力例 2
5 20 1 8 5 10 13
出力例 2
-1
入力例 3
10 100000 73766 47718 74148 49218 76721 31902 21994 18880 29598 98917
出力例 3
4 6 8
Score : 600 points
Problem Statement
You are given an integer sequence A = (A_1, A_2, \dots, A_N) and an integer X.
Print one triple of integers (i, j, k) satisfying all of the following conditions. If no such triple exists, report that fact.
- 1 \leq i \lt j \lt k \leq N
- A_i + A_j + A_k = X
Constraints
- 3 \leq N \leq 10^6
- 1 \leq X \leq 10^6
- 1 \leq A_i \leq X
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N X A_1 A_2 \dots A_N
Output
If there exists an integer triple (i, j, k) satisfying the conditions, print one in the following format. If there are multiple solutions, you may print any of them.
i j k
If no such triple exists, print -1.
Sample Input 1
5 16 1 8 5 10 13
Sample Output 1
1 3 4
The triple (i, j, k) = (1, 3, 4) satisfies 1 \leq i \lt j \lt k \leq N and A_i + A_j + A_k = 1 + 5 + 10 = 16 = X.
Sample Input 2
5 20 1 8 5 10 13
Sample Output 2
-1
Sample Input 3
10 100000 73766 47718 74148 49218 76721 31902 21994 18880 29598 98917
Sample Output 3
4 6 8
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 800 点
問題文
頂点に 0, 1, \dots, N \times M の番号がついた N \times M + 1 頂点の木があります。i 本目の辺 (1 \leq i \leq N \times M) は頂点 i と頂点 \max(i - N, 0) を結ぶ辺です。
また、頂点 0 には色が塗られています。それ以外の頂点は色が塗られていません。
高橋君は頂点 0 にいます。高橋君は色が塗られていない頂点が存在する間、次の操作を行います。
- 自身がいる頂点に隣接する頂点の中から一様ランダムに頂点を 1 つ選んで、その頂点に移動する。(全ての選択は独立である。) そして、今いる頂点に色が塗られていなければ色を塗る。
操作を行う回数の期待値を \text{mod }998244353 で求めてください。
期待値 \text{mod }{998244353} の定義
求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \not \equiv 0 \pmod{998244353} となることも証明できます。このとき、R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353 を満たす整数 R が一意に定まります。この R を答えてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- N, M は整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
操作を行う回数の期待値を \text{mod }998244353 で出力せよ。
入力例 1
2 2
出力例 1
20
高橋君は例えば以下のように行動します。
- 頂点 1 に移動して、頂点に色を塗る。この行動が選択される確率は \frac{1}{2} である。
- 頂点 0 に移動する。この行動が選択される確率は \frac{1}{2} である。
- 頂点 1 に移動する。この行動が選択される確率は \frac{1}{2} である。
- 頂点 3 に移動して、頂点に色を塗る。この行動が選択される確率は \frac{1}{2} である。
- 頂点 1 に移動する。この行動が選択される確率は 1 である。
- 頂点 0 に移動する。この行動が選択される確率は \frac{1}{2} である。
- 頂点 2 に移動して、頂点に色を塗る。この行動が選択される確率は \frac{1}{2} である。
- 頂点 4 に移動して、頂点に色を塗る。この行動が選択される確率は \frac{1}{2} である。
高橋君がこのように行動する確率は \frac{1}{128} で、この時の操作回数は 8 回です。また、操作回数の期待値は 20 回です。
入力例 2
123456 185185
出力例 2
69292914
Score : 800 points
Problem Statement
There is a tree with N \times M + 1 vertices numbered 0, 1, \dots, N \times M. The i-th edge (1 \leq i \leq N \times M) connects vertices i and \max(i - N, 0).
Vertex 0 is painted. The other vertices are unpainted.
Takahashi is at vertex 0. As long as there exists an unpainted vertex, he performs the following operation:
- He chooses one of the vertices adjacent to his current vertex uniformly at random (all choices are independent) and moves to that vertex. Then, if the vertex he is on is unpainted, he paints it.
Find the expected number of times he performs the operation, modulo 998244353.
What is the expected value modulo 998244353?
It can be proved that the sought expected value is always rational. Under the constraints of this problem, when that value is expressed as an irreducible fraction \frac{P}{Q}, it can also be proved that Q \not\equiv 0 \pmod{998244353}. Then, there uniquely exists an integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353. Report this R.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- N and M are integers.
Input
The input is given from Standard Input in the following format:
N M
Output
Print the expected number of times he performs the operation, modulo 998244353.
Sample Input 1
2 2
Sample Output 1
20
For example, Takahashi could behave as follows.
- Moves to vertex 1 and paints it. This action is chosen with probability \frac{1}{2}.
- Moves to vertex 0. This action is chosen with probability \frac{1}{2}.
- Moves to vertex 1. This action is chosen with probability \frac{1}{2}.
- Moves to vertex 3 and paints it. This action is chosen with probability \frac{1}{2}.
- Moves to vertex 1. This action is chosen with probability 1.
- Moves to vertex 0. This action is chosen with probability \frac{1}{2}.
- Moves to vertex 2 and paints it. This action is chosen with probability \frac{1}{2}.
- Moves to vertex 4 and paints it. This action is chosen with probability \frac{1}{2}.
He behaves in this way with probability \frac{1}{128}, in which case the number of operations is 8. The expected number of operations is 20.
Sample Input 2
123456 185185
Sample Output 2
69292914
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 800 点
問題文
正整数列 B = (B_1, B_2, \dots, B_k) の スコア を \displaystyle \sum_{i=1}^{k-1} \gcd(B_i, B_{i+1}) として定義します。
長さ N の正整数列 A = (A_1, A_2, \dots, A_N) が与えられるので、m = 1, 2, \dots, N に対して次の問題を解いてください。
- 列 (A_1, A_2, \dots, A_m) の空でない部分列は 2^m - 1 通りありますが、それらのスコアの総和を 998244353 で割った余りを求めてください。ただし、2 つの部分列が列として同じでも、取り出す位置が異なるならば区別するものとします。
制約
- 1 \leq N \leq 5 \times 10^5
- 1 \leq A_i \leq 10^5
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
N 行出力せよ。i 行目には m = i の時の答えを出力せよ。
入力例 1
3 9 6 4
出力例 1
0 3 11
m = 3 の時を考えます。(A_1, A_2, A_3) = (9, 6, 4) の空でない部分列、およびそのスコアを列挙すると次のようになります。
- (9) : スコアは 0 です。
- (6) : スコアは 0 です。
- (4) : スコアは 0 です。
- (9, 6) : スコアは \gcd(9, 6) = 3 です。
- (9, 4) : スコアは \gcd(9, 4) = 1 です。
- (6, 4) : スコアは \gcd(6, 4) = 2 です。
- (9, 6, 4) : スコアは \gcd(9, 6) + \gcd(6, 4) = 3 + 2 = 5 です。
以上より、m = 3 の時の答えは 0 + 0 + 0 + 3 + 1 + 2 + 5 = 11 となります。
入力例 2
5 3 8 12 6 9
出力例 2
0 1 13 57 155
入力例 3
10 47718 21994 74148 76721 98917 73766 29598 59035 69293 29127
出力例 3
0 2 14 35 97 372 866 1859 4273 43287
Score : 800 points
Problem Statement
Define the score of a sequence of positive integers B = (B_1, B_2, \dots, B_k) as \displaystyle \sum_{i=1}^{k-1} \gcd(B_i, B_{i+1}).
Given a sequence of positive integers A = (A_1, A_2, \dots, A_N), solve the following problem for m = 1, 2, \dots, N.
- There are 2^m - 1 non-empty subsequences of the sequence (A_1, A_2, \dots, A_m). Find the sum of the scores of all those subsequences, modulo 998244353. Two subsequences are distinguished if they are taken from different positions in the sequence, even if they coincide as sequences.
Constraints
- 1 \leq N \leq 5 \times 10^5
- 1 \leq A_i \leq 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print N lines. The i-th line should contain the answer for m = i.
Sample Input 1
3 9 6 4
Sample Output 1
0 3 11
Consider the case m = 3. Here are the non-empty subsequences of (A_1, A_2, A_3) = (9, 6, 4) and their scores.
- (9): Score is 0.
- (6): Score is 0.
- (4): Score is 0.
- (9, 6): Score is \gcd(9, 6) = 3.
- (9, 4): Score is \gcd(9, 4) = 1.
- (6, 4): Score is \gcd(6, 4) = 2.
- (9, 6, 4): Score is \gcd(9, 6) + \gcd(6, 4) = 3 + 2 = 5.
Therefore, the answer for m = 3 is 0 + 0 + 0 + 3 + 1 + 2 + 5 = 11.
Sample Input 2
5 3 8 12 6 9
Sample Output 2
0 1 13 57 155
Sample Input 3
10 47718 21994 74148 76721 98917 73766 29598 59035 69293 29127
Sample Output 3
0 2 14 35 97 372 866 1859 4273 43287