問題文

長さ N の文字列 S があります。S の各文字は \mathtt{A},\mathtt{B},\mathtt{C} のいずれかです。

これから S に以下の操作を K 回行います。最終的な S としてありえる文字列の数を 998244353 で割った余りを求めてください。

• 1\leq i\leq |S|-1 を満たす整数 i を選ぶ。S の i 文字目と i+1 文字目が等しいならば、S の i 文字目の直後に S の i 文字目と等しい文字を挿入する。そうでないならば、S の i 文字目の直後に \mathtt{A},\mathtt{B},\mathtt{C} のうち S の i 文字目と i+1 文字目のどちらとも等しくないものを挿入する。

制約

• 2\leq N\leq 2\times 10^5
• 1\leq K\leq 2\times 10^5
• S は \mathtt{A},\mathtt{B},\mathtt{C} のみからなる長さ N の文字列

入力例 1

4 2
AABB

出力例 1

7

例えば、以下の手順で \mathtt{AABCBB} を作ることができます。

1. i=2 とする。S の 2 文字目の直後に \mathtt{C} を挿入する。
2. i=2 とする。S の 2 文字目の直後に \mathtt{B} を挿入する。

入力例 2

2 10
CC

出力例 2

1

入力例 3

19 21
AABCBAACCCACACCCBAB

出力例 3

957795267

問題文

長さ n\geq 2 の非負整数列 a=(a_1,a_2,\ldots,a_n) について、f(a) を以下の値として定義します。

• 次の操作を行って a の全ての要素を 0 に等しくできるならば、そうするために必要な操作回数の最小値。できないならば -1。
  • 1\leq i\leq n,1\leq j\leq n,|i-j|=1 を満たす整数 i,j を選ぶ。a_i を a_i\operatorname{AND}a_j で置き換える。

長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。Q 個のクエリを処理してください。

i 番目のクエリでは整数 L_i,R_i が与えられるので、f((A_{L_i},A_{L_i+1},\ldots,A_{R_i})) を求めてください。

制約

• 2\leq N\leq 2\times 10^5
• 0\leq A_i\lt 2^{30}
• 1\leq Q\leq 2\times 10^5
• 1\leq L_i\lt R_i\leq N

入力例 1

3
5 6 11
2
1 3
2 3

出力例 1

4
-1

1 番目のクエリでは、a=(5,6,11) として f(a) の値を出力します。a が (5,6,11)\rightarrow(5,4,11)\rightarrow(5,0,11)\rightarrow(5,0,0)\rightarrow(0,0,0) と変化するように操作を行うと、4 回の操作で a の要素を全て 0 と等しくできます。4 回より少ない操作手順は存在しないことが証明できるので、f(a)=4 となります。

2 番目のクエリでは、a=(6,11) として f(a) の値を出力します。どのように操作を行っても a の全ての要素を 0 と等しくすることはできないことが証明できるので、f(a)=-1 となります。

入力例 2

10
1017 40 583 310 485 428 726 123 143 962
10
2 3
2 10
3 10
5 8
5 6
5 6
3 8
6 7
1 9
1 9

出力例 2

2
9
9
5
-1
-1
7
-1
9
9

問題文

T 個のテストケースについて、以下の問題を解いてください。

3 枚の皿があり、皿 1 には A 枚、皿 2 には B 枚、皿 3 には C 枚のコインが乗っています。これらを用いて Alice と Bob がゲームをします。Alice が先手を取り、2 人で以下の行動を交互に行います。

行動：次の 2 つのうちいずれかを選び、行う。

• 正整数 x を選ぶ。皿 1 と 2 の両方から x 枚ずつコインを取り除く。
• 正整数 x を選ぶ。皿 2 と 3 の両方から x 枚ずつコインを取り除く。

行動ができなかった人が負け、負けなかった人が勝ちます。Alice と Bob のどちらに必勝法があるか判定してください。

制約

• 1\leq T\leq 2\times 10^5
• 1\leq A,B,C\leq 10^9

入力例 1

4
3 8 4
10 10 10
131 313 131
314159265 358979323 846264338

出力例 1

Alice
Alice
Bob
Alice

例えば、1 番目のテストケースに対しては次のようなゲームの進行が考えられます。

1. Alice が皿 1 と 2 の両方から 2 枚ずつコインを取り除く。
2. Bob が皿 2 と 3 の両方から 1 枚ずつコインを取り除く。
3. Alice が皿 2 と 3 の両方から 2 枚ずつコインを取り除く。
4. Bob が皿 2 と 3 の両方から 1 枚ずつコインを取り除く。
5. Alice が皿 1 と 2 の両方から 1 枚ずつコインを取り除く。

最終的に皿 2 にのみコインが 1 枚残り、Bob は操作ができなくなります。この進行はあくまで一例であり、必ずしも最適な行動をとっているとは限りませんが、このテストケースでは Alice に必勝法があることが証明できます。

問題文

以下の条件を満たす長さ 30 の正整数列 a=(a_1,a_2,\ldots,a_{30}) を出力してください。

• 1 \le a_i \le 10^{18}\ (1 \le i \le 30)
• すべての連続する区間の最大公約数が相異なる。より形式的には、 (i,j)\ (1 \le i \le j \le 30) と (k,l)\ (1\le k \le l \le 30) について、 (i,j) \neq (k,l) ならば、 \gcd(a_i,a_{i+1},\ldots,a_j)\neq \gcd(a_k,a_{k+1},\ldots,a_l) を満たす。

問題文

0 以上 M 以下の整数からなる数列 A=(A_1,A_2,\ldots,A_N) であって、次の条件を満たすものの数を、998244353 で割った余りを求めてください。

• B_i=\operatorname{mex}(\lbrace A_i,A_{i+1},\ldots,A_{i+K-1}\rbrace) として数列 B=(B_1,B_2,\ldots,B_{N-K+1}) を作ったとき、B は狭義単調増加である。つまり、B_1\lt B_2\lt\cdots\lt B_{N-K+1} を満たす。

制約

• 1\leq N\leq 2\times 10^5
• 1\leq M\leq 2\times 10^5
• 1\leq K\leq N

入力例 1

3 1 2

出力例 1

2

(0,0,1) と (1,1,0) の 2 つが条件を満たします。

入力例 2

4 4 1

出力例 2

0

入力例 3

271 828 182

出力例 3

125683497

問題文

正整数 N、非負整数 K、長さ N の非負整数列 A=(A_{1},A_{2},\ldots,A_{N}) が与えられます。

整数組 (L,R) であって 1\leq L\leq R\leq N かつ \operatorname{mex}(\lbrace A_{L},A_{L+1},\ldots,A_{R}\rbrace)=K を満たすものの個数を計算してください。

制約

• 1\leq N\leq 2\times 10^{5}
• 0\leq K\leq N
• 0\leq A_i\leq N

入力例 1

5 2
0 1 2 1 0

出力例 1

2

条件を満たす (L,R) は (1,2) と (4,5) の 2 つです。

入力例 2

5 0
1 2 3 4 5

出力例 2

15

入力例 3

10 2
0 1 1 3 1 0 2 1 0 4

出力例 3

11

問題文

T 個のテストケースについて、以下の問題を解いてください。

長さ N の数列 A=(A_1,A_2,\ldots,A_N) があり、現在全ての 1\leq i\leq N について A_i=0 です。

あなたの目標は全ての 1\leq i\leq N について A_i\equiv R_i\pmod{M} が成立するようにすることです。これを実現させるため、以下の操作を任意の回数行うことができます。(一度も行わないこともできます。)

• 1\leq j\leq K を満たす整数 j を選ぶ。A の P_j 番目の要素に 1 を加える。さらに、A の Q_j 番目の要素に 1 を加える。

目標が達成可能かどうかを判定してください。

制約

• 1\leq T\leq 2\times 10^5
• 1\leq N\leq 2\times 10^5
• 2\leq M\leq 10^9
• 1\leq K\leq 2\times 10^5
• 0\leq R_i\lt M
• 1\leq P_i\leq N
• 1\leq Q_i\leq N
• 1 つの入力に含まれる N の総和、K の総和はそれぞれ 2\times 10^5 を超えない

入力例 1

3
6 3 5
0 1 0 1 2 0
1 2
1 6
4 5
5 2
5 6
6 4 7
2 3 1 2 3 0
1 4
3 2
3 5
6 5
4 6
1 2
2 4
4 5 4
2 4 2 4
1 3
1 3
2 4
2 4

出力例 1

Yes
No
Yes

1 番目のテストケースでは、次の順序で操作を行うことで目標が達成できます。

1. j=2 とする。A=(1,0,0,0,0,1) になる。
2. j=1 とする。A=(2,1,0,0,0,1) になる。
3. j=2 とする。A=(3,1,0,0,0,2) になる。
4. j=3 とする。A=(3,1,0,1,1,2) になる。
5. j=5 とする。A=(3,1,0,1,2,3) になる。

最終的に全ての 1\leq i\leq 6 について A_i\equiv R_i\pmod{3} とできていることが確認できます。

問題文

空でない文字列 X と非負整数 K に対して、\operatorname{rot}(X,K) を次のように定めます。

• X の先頭の文字を末尾に移動させるという操作を K 回行った結果得られる文字列。

長さの等しい空でない文字列 X, Y に対し、f(X, Y) を次のように定めます。

• 0\leq i\lt|X| かつ \operatorname{rot}(X,i) が \operatorname{rot}(Y,i) よりも辞書順で小さくなるような整数 i の個数。

正整数 N と、ともに長さが N である文字列 S,T が与えられます。以下の 2 種類のクエリが合計で Q 個与えられるので処理してください。

• クエリ 1: 整数 L,R が与えられる。S の L 文字目から R 文字目までを抜き出して得られる文字列を S'、T の L 文字目から R 文字目までを抜き出して得られる文字列を T' として、f(S',T') を求める。
• クエリ 2: 整数 X, Y と英小文字 C が与えられる。X = 1 のとき S の Y 文字目を C で置き換える。X = 2 のとき T の Y 文字目を C で置き換える。

制約

• 1\leq N\leq 2\times 10^{5}
• S と T は英小文字からなる長さ N の文字列
• 1\leq Q\leq 2\times 10^{5}
• クエリ 1 について、1\leq L\leq R\leq N
• クエリ 2 について、X\in\lbrace 1,2\rbrace,1\leq Y\leq N であり、C は英小文字

入力例 1

9
dacbyzyzx
dcabzyzyx
6
1 2 4
1 5 9
2 1 1 z
1 1 1
2 2 9 a
1 6 9

出力例 1

2
3
0
1

1 番目のクエリについて説明します。S'=\mathtt{acb},T'=\mathtt{cab} であり、f(S',T') を出力する必要があります。

• \operatorname{rot}(S',0)=\mathtt{acb},\operatorname{rot}(T',0)=\mathtt{cab}
• \operatorname{rot}(S',1)=\mathtt{cba},\operatorname{rot}(T',1)=\mathtt{abc}
• \operatorname{rot}(S',2)=\mathtt{bac},\operatorname{rot}(T',2)=\mathtt{bca}

ですから、このクエリに対する出力は 2 です。

入力例 2

20
pilrajvvuwrcxvbchgyf
pitlabnvzyrmoveahgyr
20
2 2 3 l
2 2 3 l
1 3 17
2 1 6 b
1 1 13
1 19 20
1 8 14
1 2 16
2 1 9 c
2 2 19 x
2 1 20 r
2 2 9 c
1 7 7
1 11 13
1 10 20
1 9 11
2 2 1 b
1 6 16
2 1 1 w
2 1 1 q

出力例 2

7
5
2
6
7
0
2
6
3
7

問題文

N 頂点の根付き木があります。頂点には 1 から N までの番号がつけられています。この木の根は頂点 1 で、2\leq i\leq N について頂点 i の親は P_i\,(P_i\lt i) です。

あなたはこれから (1,2,\ldots,N) の順列 Q=(Q_1,Q_2,\ldots,Q_N) を 1 つ決めます。すると、各 1\leq i\leq N について、頂点 Q_i が頂点 V_i の部分木内にあるときにコスト C_i が発生します。

発生するコストの総和の最小値を計算してください。

制約

• 2\leq N\leq2\times10^5
• 1\leq P_i\lt i
• 1\leq V_i\leq N
• 1\leq C_i\leq10^9

入力例 1

3
1 2
2 2 2
1 2 3

出力例 1

3

Q=(3,2,1) とすると、発生するコストの総和は 1+2=3 です。これが最小値です。

入力例 2

5
1 1 1 1
1 2 3 4 5
5 4 3 2 1

出力例 2

5

入力例 3

9
1 2 3 2 3 2 3 2
2 2 2 3 3 2 3 2 3
124 981 554 92 498 327 613 709 192

出力例 3

1714

問題文

T 個のテストケースについて、以下の問題を解いてください。

非負整数 L,R\,(L\leq R) が与えられます。\lbrace L,L+1,\ldots,R\rbrace の部分集合を 1 つ選ぶとき、その集合に含まれる数の総 XOR としてありえる整数はいくつありますか？ただし、0 個の数の XOR は 0 とします。

制約

• 1\leq T\leq 2\times 10^5
• 0\leq L\leq R\lt 2^{60}

入力例 1

3
8 10
2 2
123 456

出力例 1

8
2
512

1 つめのテストケースについて説明します。総 XOR としてありえる整数は 0,1,2,3,8,9,10,11 の 8 つです。例えば、\lbrace 8,9,10\rbrace の部分集合として \lbrace 8,10\rbrace を選べば総 XOR が 2 になります。