Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
整数 A, B が与えられます。 A^B の値を出力してください。
制約
- 1 \leq A, B \leq 9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
答えを出力せよ。
入力例 1
4 3
出力例 1
64
4^3 = 64 であるので、64 を出力します。
入力例 2
5 5
出力例 2
3125
入力例 3
8 1
出力例 3
8
Score : 100 points
Problem Statement
Given integers A and B, print the value A^B.
Constraints
- 1 \leq A, B \leq 9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
A B
Output
Print the answer.
Sample Input 1
4 3
Sample Output 1
64
4^3 = 64, so 64 should be printed.
Sample Input 2
5 5
Sample Output 2
3125
Sample Input 3
8 1
Sample Output 3
8
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
整数 N と長さ N の数列 A=(A _ 1,A _ 2,\ldots,A _ N) が与えられます。
クエリが Q 個与えられるので、与えられた順番に処理してください。 クエリは次の 2 種類のいずれかです。
1 k x
: A _ k の値を x に変更する。2 k
: A _ k の値を出力する。
制約
- 1 \leq N \leq 10 ^ 5
- 1 \leq Q \leq 10 ^ 5
- 0 \leq A _ i \leq 10 ^ 9\ (1\leq i\leq N)
- どのクエリについても、1\leq k\leq N
- 1 番目の形式のクエリについて、0\leq x\leq 10 ^ 9
- 2 番目の形式のクエリが 1 つ以上存在する
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A _ 1 A _ 2 \ldots A _ N Q \operatorname{query} _ 1 \operatorname{query} _ 2 \vdots \operatorname{query} _ Q
ただし、\operatorname{query} _ i は i 個目のクエリを表しており、次の形式のいずれかで与えられる。
1 k x
2 k
出力
2 番目の形式のクエリの回数を q 回として q 行出力せよ。 j\ (1\leq j\leq q) 行目には、2 番目の形式のクエリのうち j 個目のものに対する答えを出力せよ。
入力例 1
3 1 3 5 7 2 2 2 3 1 3 0 2 3 1 2 8 2 2 2 1
出力例 1
3 5 0 8 1
はじめ、A=(1,3,5) です。
- 1 つめのクエリにおいて、A=(1,3,5) です。A _ 2=3 なので、3 を出力します。
- 2 つめのクエリにおいて、A=(1,3,5) です。A _ 3=5 なので、5 を出力します。
- 3 つめのクエリでは、A _ 3 の値を 0 に変更し、A=(1,3,0) となります。
- 4 つめのクエリにおいて、A=(1,3,0) です。A _ 3=0 なので、0 を出力します。
- 5 つめのクエリでは、A _ 2 の値を 8 に変更し、A=(1,8,0) となります。
- 6 つめのクエリにおいて、A=(1,8,0) です。A _ 2=8 なので、8 を出力します。
- 7 つめのクエリにおいて、A=(1,8,0) です。A _ 1=1 なので、1 を出力します。
入力例 2
5 22 2 16 7 30 10 1 4 0 1 5 0 2 2 2 3 2 4 2 5 1 4 100 1 5 100 2 3 2 4
出力例 2
2 16 0 0 16 100
入力例 3
7 478 369 466 343 541 42 165 20 2 1 1 7 729 1 6 61 1 6 838 1 3 319 1 4 317 2 4 1 1 673 1 3 176 1 5 250 1 1 468 2 6 1 7 478 1 5 595 2 6 1 6 599 1 6 505 2 3 2 5 2 1
出力例 3
478 317 838 838 176 595 468
Score : 200 points
Problem Statement
You are given an integer N and a sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N.
Given Q queries, process them in the given order. Each query is of one of the following two kinds:
1 k x
: set the value A _ k to x.2 k
: print the value A _ k.
Constraints
- 1 \leq N \leq 10 ^ 5
- 1 \leq Q \leq 10 ^ 5
- 0 \leq A _ i \leq 10 ^ 9\ (1\leq i\leq N)
- 1\leq k\leq N for all queries.
- 0\leq x\leq 10 ^ 9 for all queries of the first kind.
- There is at least one query of the second kind.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A _ 1 A _ 2 \ldots A _ N Q \operatorname{query} _ 1 \operatorname{query} _ 2 \vdots \operatorname{query} _ Q
Here, \operatorname{query} _ i denotes the i-th query, given in one of the following formats:
1 k x
2 k
Output
Print q lines, where q is the number of queries of the second kind. The j-th (1\leq j\leq q) line should contain the response to the j-th such query.
Sample Input 1
3 1 3 5 7 2 2 2 3 1 3 0 2 3 1 2 8 2 2 2 1
Sample Output 1
3 5 0 8 1
Initially, A=(1,3,5).
- For the 1-st query, A=(1,3,5), where A _ 2=3, so 3 should be printed.
- For the 2-nd query, A=(1,3,5), where A _ 3=5, so 5 should be printed.
- The 3-rd query sets the value A _ 3 to 0, making A=(1,3,0).
- For the 4-th query, A=(1,3,0), where A _ 3=0, so 0 should be printed.
- The 5-th query sets the value A _ 2 to 8, making A=(1,8,0).
- For the 6-th query, A=(1,8,0), where A _ 2=8, so 8 should be printed.
- For the 7-th query, A=(1,8,0), where A _ 1=1, so 1 should be printed.
Sample Input 2
5 22 2 16 7 30 10 1 4 0 1 5 0 2 2 2 3 2 4 2 5 1 4 100 1 5 100 2 3 2 4
Sample Output 2
2 16 0 0 16 100
Sample Input 3
7 478 369 466 343 541 42 165 20 2 1 1 7 729 1 6 61 1 6 838 1 3 319 1 4 317 2 4 1 1 673 1 3 176 1 5 250 1 1 468 2 6 1 7 478 1 5 595 2 6 1 6 599 1 6 505 2 3 2 5 2 1
Sample Output 3
478 317 838 838 176 595 468
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
高橋君は、レジ打ちの仕事をしています。
レジの機械には 00
, 0
, 1
, 2
, 3
, 4
, 5
, 6
, 7
, 8
, 9
の 11 個のボタンがあります。
レジの機械には、はじめ 0 が表示されています。
ボタン 00
を押すと、表示されている数が 100 倍されます。
それ以外のボタンを押すと、表示されている数が 10 倍されたあとに、押されたボタンに書かれている数が加算されます。
高橋君は、レジに整数 S を表示させたいです。 レジに S が表示されている状態にするためには、少なくとも何回ボタンを押す必要があるか求めてください。
制約
- 1\leq S\leq 10^{100000}
- S は整数
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを 1 行で出力せよ。
入力例 1
40004
出力例 1
4
例えば、次のように操作することでボタンを 4 回押して 40004 を表示させることができます。 はじめ、レジには 0 が表示されています。
- ボタン
4
を押す。レジに表示されている数は 4 となる。 - ボタン
00
を押す。レジに表示されている数は 400 となる。 - ボタン
0
を押す。レジに表示されている数は 4000 となる。 - ボタン
4
を押す。レジに表示されている数は 40004 となる。
3 回までボタンを押すことでレジに 40004 を表示させることはできないので、出力すべき値は 4 です。
入力例 2
1355506027
出力例 2
10
入力例 3
10888869450418352160768000001
出力例 3
27
S は 64\operatorname{bit} 整数に収まらない場合があることに注意してください。
Score : 300 points
Problem Statement
Takahashi is a cashier.
There is a cash register with 11 keys: 00
, 0
, 1
, 2
, 3
, 4
, 5
, 6
, 7
, 8
, and 9
.
The cash register initially displays 0.
Whenever he types the key 00
, the displayed number is multiplied by 100;
whenever he types one of the others, the displayed number is multiplied by 10, and then added by the number written on the key.
Takahashi wants the cash register to display an integer S. At least how many keystrokes are required to make it display S?
Constraints
- 1\leq S\leq 10^{100000}
- S is an integer.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer in a line.
Sample Input 1
40004
Sample Output 1
4
For example, the following four keystrokes make the cash register display 40004. Initially, the cash register displays 0.
- Type the key
4
. It now displays 4. - Type the key
00
. It now displays 400. - Type the key
0
. It now displays 4000. - Type the key
4
. It now displays 40004.
He cannot make it display 40004 with three or fewer keystrokes, so 4 should be printed.
Sample Input 2
1355506027
Sample Output 2
10
Sample Input 3
10888869450418352160768000001
Sample Output 3
27
Note that S may not fit into a 64-\operatorname{bit} integer type.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
英小文字、(
、)
からなる文字列のうち、以下の手順によって空文字列になるものを良い文字列と呼びます:
- まず、英小文字をすべて削除する。
- 次に、連続する
()
が存在する限り、それを削除する。
例えば、((a)ba)
は英小文字をすべて削除すると (())
となり、2 文字目と 3 文字目に連続する ()
を削除すると ()
となり、最終的に空文字列にすることができるので良い文字列です。
良い文字列 S が与えられます。 S の i 文字目を S_i で表します。
各英小文字 a
, b
, \ldots , z
に対して、その文字が書かれたボールが 1 つあります。
また、空の箱があります。
高橋君は i = 1,2, \ldots ,|S| に対してこの順に気を失わない限り操作を行います。
- S_i が英小文字ならば、その英小文字が書かれたボールを箱に入れる。ただし、そのボールがすでに箱に入っている場合、高橋君は気を失う。
- S_i が
(
ならば、何もしない。 - S_i が
)
ならば、i 未満の整数 j であって、S の j 番目から i 番目までの文字からなる文字列が良い文字列となる最大の整数 j を取る。(このような整数 j は必ず存在することが証明できる。)j 番目から i 番目までの操作で箱に入れたボールをすべて、箱から取り出す。
高橋君が気を失わずに一連の操作を完了させられるか判定してください。
制約
- 1 \leq |S| \leq 3 \times 10^5
- S は良い文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
高橋君が気を失わずに一連の操作を完了させられる場合は Yes
を、そうでない場合は No
を出力せよ。
入力例 1
((a)ba)
出力例 1
Yes
i = 1 のとき、高橋君は何もしません。
i = 2 のとき、高橋君は何もしません。
i = 3 のとき、高橋君は a
の書かれたボールを箱の中に入れます。
i = 4 のとき、4 未満の整数 j であって、S の j 番目から 4 番目までの文字からなる文字列が良い文字列となる最大の整数は 2 であるため、高橋君は a
の書かれたボールを箱から取り出します。
i = 5 のとき、高橋君は b
の書かれたボールを箱の中に入れます。
i = 6 のとき、高橋君は a
の書かれたボールを箱の中に入れます。
i = 7 のとき、7 未満の整数 j であって、S の j 番目から 7 番目までの文字からなる文字列が良い文字列となる最大の整数は 1 であるため、高橋君は a
の書かれたボールと b
の書かれたボールを箱から取り出します。
したがってこの場合の答えは Yes
となります。
入力例 2
(a(ba))
出力例 2
No
i = 1 のとき、高橋君は何もしません。
i = 2 のとき、高橋君は a
の書かれたボールを箱の中に入れます。
i = 3 のとき、高橋君は何もしません。
i = 4 のとき、高橋君は b
の書かれたボールを箱の中に入れます。
i = 5 のとき、a
の書かれたボールはすでに箱に入っているため、高橋君は気を失い、これ以降の操作は行われません。
したがってこの場合の答えは No
となります。
入力例 3
(((())))
出力例 3
Yes
入力例 4
abca
出力例 4
No
Score : 400 points
Problem Statement
A string consisting of lowercase English letters, (
, and )
is said to be a good string if you can make it an empty string by the following procedure:
- First, remove all lowercase English letters.
- Then, repeatedly remove consecutive
()
while possible.
For example, ((a)ba)
is a good string, because removing all lowercase English letters yields (())
, from which we can remove consecutive ()
at the 2-nd and 3-rd characters to obtain ()
, which in turn ends up in an empty string.
You are given a good string S. We denote by S_i the i-th character of S.
For each lowercase English letter a
, b
, \ldots, and z
, we have a ball with the letter written on it.
Additionally, we have an empty box.
For each i = 1,2, \ldots ,|S| in this order, Takahashi performs the following operation unless he faints.
- If S_i is a lowercase English letter, put the ball with the letter written on it into the box. If the ball is already in the box, he faints.
- If S_i is
(
, do nothing. - If S_i is
)
, take the maximum integer j less than i such that the j-th through i-th characters of S form a good string. (We can prove that such an integer j always exists.) Take out from the box all the balls that he has put in the j-th through i-th operations.
Determine if Takahashi can complete the sequence of operations without fainting.
Constraints
- 1 \leq |S| \leq 3 \times 10^5
- S is a good string.
Input
The input is given from Standard Input in the following format:
S
Output
Print Yes
if he can complete the sequence of operations without fainting; print No
otherwise.
Sample Input 1
((a)ba)
Sample Output 1
Yes
For i = 1, he does nothing.
For i = 2, he does nothing.
For i = 3, he puts the ball with a
written on it into the box.
For i = 4, j=2 is the maximum integer less than 4 such that the j-th through 4-th characters of S form a good string, so he takes out the ball with a
written on it from the box.
For i = 5, he puts the ball with b
written on it into the box.
For i = 6, he puts the ball with a
written on it into the box.
For i = 7, j=1 is the maximum integer less than 7 such that the j-th through 7-th characters of S form a good string, so he takes out the ball with a
written on it, and another with b
, from the box.
Therefore, the answer to this case is Yes
.
Sample Input 2
(a(ba))
Sample Output 2
No
For i = 1, he does nothing.
For i = 2, he puts the ball with a
written on it into the box.
For i = 3, he does nothing.
For i = 4, he puts the ball with b
written on it into the box.
For i = 5, the ball with a
written on it is already in the box, so he faints, aborting the sequence of operations.
Therefore, the answer to this case is No
.
Sample Input 3
(((())))
Sample Output 3
Yes
Sample Input 4
abca
Sample Output 4
No
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
各要素の値が 0 または 1 である H 行 W 列の行列 A が与えられます。 1 \leq i \leq H かつ 1 \leq j \leq W を満たす整数の組 (i,j) について、A の i 行目 j 列目の要素を A_{i,j} で表します。
行列 A に対し、以下の操作を 0 回以上の好きな回数行うことができます。
- 1 \leq i \leq H を満たす整数 i を選び、1 \leq j \leq W を満たす全ての整数 j に対して A_{i,j} の値を 1-A_{i,j} で置き換える。
また、A_{i,j} は行列において上下左右に同じ値が存在しない、すなわち 4 つの整数組 (x,y) = (i-1,j),(i+1,j),(i,j-1),(i,j+1) のいずれかであって、 1 \leq x \leq H, 1 \leq y \leq W かつ A_{i,j} = A_{x,y} を満たすものが存在しないとき、またそのときに限り孤立した要素であると定義されます。
操作を繰り返し行列 A の任意の要素が孤立した要素でない状態にすることが可能か判定し、可能な場合は行う操作回数の最小値を求めてください。
制約
- 2 \leq H,W \leq 1000
- A_{i,j} = 0 または A_{i,j} = 1
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
H W A_{1,1} A_{1,2} \ldots A_{1,W} A_{2,1} A_{2,2} \ldots A_{2,W} \vdots A_{H,1} A_{H,2} \ldots A_{H,W}
出力
操作を繰り返すことにより孤立した要素が存在しないようにできる場合は操作回数の最小値を、できない場合は -1
を出力せよ。
入力例 1
3 3 1 1 0 1 0 1 1 0 0
出力例 1
1
i = 1 を選択し操作を行うと、A = ((0,0,1),(1,0,1),(1,0,0)) となり、孤立した要素は存在しなくなります。
入力例 2
4 4 1 0 0 0 0 1 1 1 0 0 1 0 1 1 0 1
出力例 2
2
入力例 3
2 3 0 1 0 0 1 1
出力例 3
-1
Score : 500 points
Problem Statement
You are given a matrix A with H rows and W columns. The value of each of its elements is 0 or 1. For an integer pair (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W, we denote by A_{i,j} the element at the i-th row and j-th column.
You can perform the following operation on the matrix A any number of times (possibly zero):
- Choose an integer i such that 1 \leq i \leq H. For every integer j such that 1 \leq j \leq W, replace the value of A_{i,j} with 1-A_{i,j}.
A_{i,j} is said to be isolated if and only if there is no adjacent element with the same value; in other words, if and only if none of the four integer pairs (x,y) = (i-1,j),(i+1,j),(i,j-1),(i,j+1) satisfies 1 \leq x \leq H, 1 \leq y \leq W, and A_{i,j} = A_{x,y}.
Determine if you can make the matrix A in such a state that no element is isolated by repeating the operation. If it is possible, find the minimum number of operations required to do so.
Constraints
- 2 \leq H,W \leq 1000
- A_{i,j} = 0 or A_{i,j} = 1
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
H W A_{1,1} A_{1,2} \ldots A_{1,W} A_{2,1} A_{2,2} \ldots A_{2,W} \vdots A_{H,1} A_{H,2} \ldots A_{H,W}
Output
If you can make it in such a state that no element is isolated by repeating the operation, print the minimum number of operations required to do so; otherwise, print -1
.
Sample Input 1
3 3 1 1 0 1 0 1 1 0 0
Sample Output 1
1
An operation with i = 1 makes A = ((0,0,1),(1,0,1),(1,0,0)), where there is no longer an isolated element.
Sample Input 2
4 4 1 0 0 0 0 1 1 1 0 0 1 0 1 1 0 1
Sample Output 2
2
Sample Input 3
2 3 0 1 0 0 1 1
Sample Output 3
-1
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
(1,2,\ldots,N) の順列 P=(P _ 1,P _ 2,\ldots,P _ N) が与えられます。
すべての i\ (1\leq i\leq N) に対して、以下の値を求めてください。
- D _ i=\displaystyle\min_{j\neq i}\left\lparen\left\lvert P _ i-P _ j\right\rvert+\left\lvert i-j\right\rvert\right\rparen
順列とは
(1,2,\ldots,N) の順列とは、(1,2,\ldots,N) を並べ替えて得られる数列のことをいいます。 つまり、長さ N の数列 A は i\ (1\leq i\leq N) がその中にちょうど 1 回だけ現れるとき、かつそのときに限り(1,2,\ldots,N) の順列です。制約
- 2 \leq N \leq 2\times10^5
- 1 \leq P _ i \leq N\ (1\leq i\leq N)
- i\neq j\implies P _ i\neq P _ j
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N P _ 1 P _ 2 \ldots P _ N
出力
D _ i\ (1\leq i\leq N) を i の昇順に空白区切りで出力せよ。
入力例 1
4 3 2 4 1
出力例 1
2 2 3 3
たとえば、i=1 について
- j=2 のとき、\left\lvert P _ i-P _ j\right\rvert=1,\left\lvert i-j\right\rvert=1 です。
- j=3 のとき、\left\lvert P _ i-P _ j\right\rvert=1,\left\lvert i-j\right\rvert=2 です。
- j=4 のとき、\left\lvert P _ i-P _ j\right\rvert=2,\left\lvert i-j\right\rvert=3 です。
よって、j=2 のとき \left\lvert P _ i-P _ j\right\rvert+\left\lvert i-j\right\rvert=2 で最小となるので、D _ 1=2 です。
入力例 2
7 1 2 3 4 5 6 7
出力例 2
2 2 2 2 2 2 2
入力例 3
16 12 10 7 14 8 3 11 13 2 5 6 16 4 1 15 9
出力例 3
3 3 3 5 3 4 3 3 4 2 2 4 4 4 4 7
Score : 500 points
Problem Statement
You are given a permutation P=(P _ 1,P _ 2,\ldots,P _ N) of (1,2,\ldots,N).
Find the following value for all i\ (1\leq i\leq N):
- D _ i=\displaystyle\min_{j\neq i}\left\lparen\left\lvert P _ i-P _ j\right\rvert+\left\lvert i-j\right\rvert\right\rparen.
What is a permutation?
A permutation of (1,2,\ldots,N) is a sequence that is obtained by rearranging (1,2,\ldots,N). In other words, a sequence A of length N is a permutation of (1,2,\ldots,N) if and only if each i\ (1\leq i\leq N) occurs in A exactly once.Constraints
- 2 \leq N \leq 2\times10^5
- 1 \leq P _ i \leq N\ (1\leq i\leq N)
- i\neq j\implies P _ i\neq P _ j
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N P _ 1 P _ 2 \ldots P _ N
Output
Print D _ i\ (1\leq i\leq N) in ascending order of i, separated by spaces.
Sample Input 1
4 3 2 4 1
Sample Output 1
2 2 3 3
For example, for i=1,
- if j=2, we have \left\lvert P _ i-P _ j\right\rvert=1 and \left\lvert i-j\right\rvert=1;
- if j=3, we have \left\lvert P _ i-P _ j\right\rvert=1 and \left\lvert i-j\right\rvert=2;
- if j=4, we have \left\lvert P _ i-P _ j\right\rvert=2 and \left\lvert i-j\right\rvert=3.
Thus, the value is minimum when j=2, where \left\lvert P _ i-P _ j\right\rvert+\left\lvert i-j\right\rvert=2, so D _ 1=2.
Sample Input 2
7 1 2 3 4 5 6 7
Sample Output 2
2 2 2 2 2 2 2
Sample Input 3
16 12 10 7 14 8 3 11 13 2 5 6 16 4 1 15 9
Sample Output 3
3 3 3 5 3 4 3 3 4 2 2 4 4 4 4 7
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
長さ N の非負整数列 A=(A _ 1,A _ 2,\ldots,A _ N) が与えられます。
非負整数列 (a _ 1,a _ 2,\ldots,a _ n) の \operatorname{xor} を、すべての非負整数 j について次の条件を満たすような整数 X と定義します。
- a _ 1,\ldots,a _ n のうち二進法で表したとき 2^j の位が 1 であるものが奇数個であるとき、かつそのときに限り 2^j の位が 1 である
非負整数の集合 \lbrace s _ 1,s _ 2,\ldots,s _ k\rbrace\ (s _ 1\lt s _ 2\lt\cdots\lt s _ k) を、A の連続とは限らない(空でもよい)部分列の \operatorname{xor} として得られる整数の集合とします。
整数 L,R が与えられるので、s _ L,s _ {L+1},\ldots,s _ R をこの順に出力してください。
制約
- 1\leq N\leq2\times10^5
- 0\leq A _ i\lt2^{60}\ (1\leq i\leq N)
- 1\leq L\leq R\leq k
- R-L\leq2\times10^5
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N L R A _ 1 A _ 2 \ldots A _ N
出力
s _ i\ (L\leq i\leq R) を i の昇順に空白区切りで出力せよ。
入力例 1
4 1 8 2 21 17 21
出力例 1
0 2 4 6 17 19 21 23
A の連続とは限らない部分列としてありえる列は (),(2),(17),(21),(2,17),(2,21),(17,21),(21,17),(21,21),(2,17,21),(2,21,17),(2,21,21),(21,17,21),(2,21,17,21) の 14 種類です。 それぞれ、 \operatorname{xor} は次のようになります。
- 空列の \operatorname{xor} は 0 です。
- (2) の \operatorname{xor} は 2 です。
- (17) の \operatorname{xor} は 17 です。
- (21) の \operatorname{xor} は 21 です。
- (2,17) の \operatorname{xor} は 19 です。
- (2,21) の \operatorname{xor} は 23 です。
- (17,21) の \operatorname{xor} は 4 です。
- (21,17) の \operatorname{xor} は 4 です。
- (21,21) の \operatorname{xor} は 0 です。
- (2,17,21) の \operatorname{xor} は 6 です。
- (2,21,17) の \operatorname{xor} は 6 です。
- (2,21,21) の \operatorname{xor} は 2 です。
- (21,17,21) の \operatorname{xor} は 17 です。
- (2,21,17,21) の \operatorname{xor} は 19 です。
よって、A の部分列のビットごとの排他的論理和としてありえる値の集合は \lbrace0,2,4,6,17,19,21,23\rbrace です。
入力例 2
4 3 7 2 21 17 21
出力例 2
4 6 17 19 21
入力例 3
5 1 1 0 0 0 0 0
出力例 3
0
入力例 4
6 21 21 88 44 82 110 121 80
出力例 4
41
入力例 5
12 26 48 19629557415 14220078328 11340722069 30701452525 22333517481 720413777 11883028647 20926361028 24376768297 720413777 27999065315 13558621130
出力例 5
13558621130 14220078328 14586054825 15518998043 15970974282 16379590008 17091531049 17412316967 17836964726 18263536708 18965057557 19629557415 20282860278 20926361028 21302757781 21908867832 22333517481 22893781403 23595304394 23723463544 24376768297 24885524507 25261923402
入力や出力が 32\operatorname{bit} 整数に収まらない場合があることに注意してください。
Score : 600 points
Problem Statement
For a sequence of non-negative integers (a _ 1,a _ 2,\ldots,a _ n), let us define its \operatorname{xor} as the integer X such that, for all non-negative integer j:
- the 2^js place of X is 1 if and only if there is an odd number of elements among a _ 1,\ldots,a _ n whose 2^js place is 1.
You are given a sequence of non-negative integers A=(A _ 1,A _ 2,\ldots,A _ N) of length N.
Let \lbrace s _ 1,s _ 2,\ldots,s _ k\rbrace\ (s _ 1\lt s _ 2\lt\cdots\lt s _ k) be the set of all non-negative integers that can be the \operatorname{xor} of a not-necessarily-contiguous (possibly empty) subsequence of A.
Given integers L and R, print s _ L,s _ {L+1},\ldots,s _ R in this order.
Constraints
- 1\leq N\leq2\times10^5
- 0\leq A _ i\lt2^{60}\ (1\leq i\leq N)
- 1\leq L\leq R\leq k
- R-L\leq2\times10^5
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N L R A _ 1 A _ 2 \ldots A _ N
Output
Print s _ i\ (L\leq i\leq R) in ascending order of i, separated by spaces.
Sample Input 1
4 1 8 2 21 17 21
Sample Output 1
0 2 4 6 17 19 21 23
There are 14 not-necessarily-contiguous subsequences of A: (),(2),(17),(21),(2,17),(2,21),(17,21),(21,17),(21,21),(2,17,21),(2,21,17),(2,21,21),(21,17,21), and (2,21,17,21), whose \operatorname{xor}s are as follows.
- The \operatorname{xor} of () is 0.
- The \operatorname{xor} of (2) is 2.
- The \operatorname{xor} of (17) is 17.
- The \operatorname{xor} of (21) is 21.
- The \operatorname{xor} of (2,17) is 19.
- The \operatorname{xor} of (2,21) is 23.
- The \operatorname{xor} of (17,21) is 4.
- The \operatorname{xor} of (21,17) is 4.
- The \operatorname{xor} of (21,21) is 0.
- The \operatorname{xor} of (2,17,21) is 6.
- The \operatorname{xor} of (2,21,17) is 6.
- The \operatorname{xor} of (2,21,21) is 2.
- The \operatorname{xor} of (21,17,21) is 17.
- The \operatorname{xor} of (2,21,17,21) is 19.
Therefore, the set of all non-negative integers that can be the \operatorname{xor} of a subsequence of A is \lbrace0,2,4,6,17,19,21,23\rbrace.
Sample Input 2
4 3 7 2 21 17 21
Sample Output 2
4 6 17 19 21
Sample Input 3
5 1 1 0 0 0 0 0
Sample Output 3
0
A may contain the same value.
Sample Input 4
6 21 21 88 44 82 110 121 80
Sample Output 4
41
Sample Input 5
12 26 48 19629557415 14220078328 11340722069 30701452525 22333517481 720413777 11883028647 20926361028 24376768297 720413777 27999065315 13558621130
Sample Output 5
13558621130 14220078328 14586054825 15518998043 15970974282 16379590008 17091531049 17412316967 17836964726 18263536708 18965057557 19629557415 20282860278 20926361028 21302757781 21908867832 22333517481 22893781403 23595304394 23723463544 24376768297 24885524507 25261923402
Note that the input and output may not fit into a 32-\operatorname{bit} integer type.
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 以上 N 以下の整数であって、M で割った余りが R になるものすべてに対する popcount の総和を求めてください。
ただし、正整数 X に対して X の popcount とは X を二進表記したときの 1 の個数、すなわち 2^k の位が 1 となる非負整数 k の個数のことです。
1 つの入力につき、 T 個のテストケースに答えてください。
制約
- 1 \leq T \leq 10^5
- 1 \leq M \leq N \leq 10^9
- 0 \leq R < M
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。入力の 1 行目は以下の通りである。
T
そして、T 個のテストケースが続く。これらはそれぞれ以下の形式で与えられる。
N M R
出力
T 行出力せよ。i 行目には i 番目のテストケースに対する答えを出力せよ。
入力例 1
2 12 5 1 6 1 0
出力例 1
6 9
1 つ目のテストケースでは、1 の popcount が 1、6 の popcount が 2、11 の popcount が 3 であるため 1+2+3 の計算結果である 6 を出力します。
2 つ目のテストケースでは、1 の popcount が 1、2 の popcount が 1、3 の popcount が 2、4 の popcount が 1、5 の popcount が 2、6 の popcount が 2 であるため 1+1+2+1+2+2 の計算結果である 9 を出力します。
Score : 600 points
Problem Statement
Find the sum of popcounts of all integers between 1 and N, inclusive, such that the remainder when divided by M equals R.
Here, the popcount of a positive integer X is the number of 1s in the binary notation of X, that is, the number of non-negative integers k such that the 2^ks place is 1.
For each input, process T test cases.
Constraints
- 1 \leq T \leq 10^5
- 1 \leq M \leq N \leq 10^9
- 0 \leq R < M
- All values in the input are integers.
Input
The input is given from Standard Input in the following format. The first line is as follows:
T
T test cases follow. Each of them is given in the following format:
N M R
Output
Print T lines. The i-th line should contain the answer to the i-th test case.
Sample Input 1
2 12 5 1 6 1 0
Sample Output 1
6 9
In the 1-st test case, the popcount of 1 is 1, the popcount of 6 is 2, and the popcount of 11 is 3, so 1+2+3=6 should be printed.
In the 2-nd test case, the popcount of 1 is 1, 2 is 1, 3 is 2, 4 is 1, 5 is 2, and 6 is 2, so 1+1+2+1+2+2=9 should be printed.