問題文

制約

• 2 \leq N \leq 2 \times 10^5
• 2 \leq K \leq 2N
• (P_1, P_2 , \cdots, P_N) は (1,2,\cdots,N) の順列
• 入力はすべて整数

入力例 1

5 4
3 2 1 4 5

出力例 1

Yes

P_1 と P_3 を入れ替えれば良いです。P_1 + P_3 = 3 + 1 \leq 4 であるため、この入れ替えが可能です。

入力例 2

4 3
2 1 4 3

出力例 2

No

たとえば P_3 と P_4 を入れ替えることはできません。 その他のどのような手順でも、P を昇順にすることはできません。

問題文

あおばさんは仙台市の大学に通う大学生です。
あおばさんは、毎日路面の積雪量によって大学への通学手段を決定します。
積雪量は降雪や融雪によって変化します。

各日の流れは以下の通りです。

• まず降雪が起こる。その日の降雪量の分だけ積雪量が増加する。
• 次に融雪が起こる。その時点での積雪量が 1 [\mathrm{cm}] 以上である場合、積雪量が 1 [\mathrm{cm}] 減少する。
• 最後にあおばさんが通学手段を決定する。その時点の積雪量がK [\mathrm{cm}] 以上ならば地下鉄を使って、K [\mathrm{cm}] 未満ならば徒歩で通学する。

仙台市の N 日間の降雪量の情報が長さ M の正整数列 a_1\lt a_2\lt \dots\lt a_M と b_1,b_2,\dots,b_M によって与えられます。
これは、a_i 日目の降雪量が b_i [\mathrm{cm}] であったことを表します。それ以外の日の降雪量は 0 [\mathrm{cm}] でした。

この N 日間のうち、あおばさんが地下鉄を使ったのは延べ何日間ありますか。
ただし、1 日目より前の積雪量は 0 [\mathrm{cm}] であったとします。

積雪量の変化の状況については入出力例1も参考にしてください。

制約

• 2 \leq N \leq 10^{12}
• 1\leq M\leq 10^5
• 1\leq K\leq 10^9
• 1 \leq a_1\lt a_2\lt \dots\lt a_M \leq N
• 1\leq b_i\le 10^9\ (i=1, 2, \dots, M)
• 入力はすべて整数

入力例 1

8 3 2
2 4
7 1
8 3

出力例 1

3

各日の積雪量の変化は以下の通りです。

よって、地下鉄を利用したのは2, 3, 8日目の3日間です。

入力例 2

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

出力例 2

5

積雪量が32bit整数に収まらない場合があります。

入力例 3

28 9 2
4 2
5 2
10 5
15 5
17 1
18 2
20 2
21 1
22 1

出力例 3

14

問題文

H 行 W 列からなるマス目があり、各マスの色は白または黒です。 i 行目 j 列目にあるマスを、マス (i,j) と呼ぶことにします。
黒いマスが N 個あり、i 番目の黒いマスは マス(x_i, y_i) です。 また、 黒くない残りの HW-N 個のマスの色は白です。

あなたはマス目に対して以下の操作を行うことができます。

• 正整数の組 (a,b) (1 \leq a \leq H, 1 \leq b \leq W) を選び、 1 \leq i \leq a かつ 1 \leq j \leq b を満たす全てのマス (i,j) の色を反転させる (白ならば黒に、黒ならば白に色を変える)。

HW 個全てのマスを白色にするために必要な操作回数の最小値を求めてください。

制約

• 1 \leq H,W \leq 2 \times 10^5
• 1 \leq N \leq \mathrm{min}(2 \times 10^5, H \times W)
• 1 \leq x_i \leq H
• 1 \leq y_i \leq W
• (x_i, y_i) \neq (x_j, y_j) (i \neq j)
• 入力はすべて整数

入力例 1

2 2 2
1 2
2 1

出力例 1

2

はじめ、マス (1,2) とマス (2,1) のみが黒いマス、それ以外が白いマスです。

まず、 (a,b) = (2,1) として操作をすることで、マス (1,1) が白から黒に変わり、マス (2,1) が黒から白に変わります。

次に、 (a,b) = (1,2) として操作をすることで、マス (1,1) とマス (1,2) が黒から白に変わります。

このように、2 回の操作で 4 マス全てを白色にすることができました。

入力例 2

2 4 3
1 2
1 3
2 3

出力例 2

4

問題文

正整数 n に対し、\zeta_n:=\cos{\left(\dfrac{2\pi}{n}\right)}+\sqrt{-1}\sin{\left(\dfrac{2\pi}{n}\right)} とします。

正整数 N が与えられるので、

\[ \sum_{a=1}^{N}\sum_{b=1}^{N}\sum_{i=0}^{a-1}\sum_{j=0}^{b-1}(\zeta_a^i+\zeta_b^j)^N \]

を求めてください。
但し、この値は整数になる事が示されます。
答えは大きくなる場合があるので、入力として与えられる素数 P で割った余りを求めてください。

制約

• 1 \leq N \leq 2\times10^5
• 10^8 \leq P \leq 10^9
• P は素数
• 入力はすべて整数

入力例 1

2 998244353

出力例 1

20

与式は (1+1)^2+(1+1)^2+(1-1)^2+(1+1)^2+(-1+1)^2+(1+1)^2+(1-1)^2+(-1+1)^2+(-1-1)^2=20 です。

入力例 2

5 998244353

出力例 2

490

入力例 3

200000 520232023

出力例 3

340864157

素数 520232023 で割った余りを求めてください。

入力例 1

7
1011110
1100111

出力例 1

1

まず、i=5 として操作 2 を行い、S= 1011011 にします。
次に、i=3 として操作 2 を行い、S= 1001111 にします。
最後に、i=2 として操作 1 を行い、S= 1100111 にします。
これにより S を T と一致させることができました。操作 1 を最低 1 回行う必要があるので答えは 1 です。

入力例 2

3
110
101

出力例 2

-1

S と T を一致させることはできません。

入力例 3

26
10101000010101010101010111
01110101000111001011010100

出力例 3

24

問題文

N \times N のマス目があります。 i = 1,2,\dots,N について、左から i 列目には下から M_i 個の 1 \times 1 の正方形のブロックがあり、それぞれのブロックには色が塗られています。ここで、 M_1,M_2,\dots,M_N は単調非増加です。左から i 列目の下から j 個目のブロックには色 C_{i,j} が塗られています。

マス目に対して、以下のような操作を考えます。

• マス目を時計回りに瞬間的に 90^\circ 回転させた後、色のついたブロックを重力に従って同時に落下させる。より形式的には、左から i 列目の下から j 個目のブロックについて、そのブロックと同じ高さでそのブロックよりも右にあるブロックが c_{i,j} 個あるとすると、このブロックを左から j 列目の下から c_{i,j}+1 番目のマスに移動させる。この移動は全てのブロックに対して同時に行う。

マス目が最初の配置に戻ってくるまでに、最小で何回の操作が必要でしょうか？ 998244353 で割った余りを求めてください。

制約

• 2 \leq N \leq 10^5
• 1 \leq \displaystyle \sum_{i=1}^N M_i \leq 10^5
• N \geq M_1 \geq M_2 \geq \dots \geq M_N \geq 0
• 1 \leq C_{i,j} \leq 10^5
• 入力はすべて整数

入力例 1

2
2 1 2
1 3

出力例 1

3

操作によって色の配置は以下のように変化します。この例では、 3 回の操作で元の状態に戻ります。

入力例 2

2
2 1 1
1 1

出力例 2

1

入力例 3

3
3 1 2 3
1 4
0

出力例 3

6

入力例 4

5
5 1 2 3 4 5
4 6 7 7 9
3 10 7 12
2 13 14
0

出力例 4

22

問題文

正整数 N が与えられます。長さ M の正整数列 A は、次の条件を満たすとき良い数列であるといいます。

• 任意の整数の組 (x,y) (1\leq x\lt y\leq N) に対して、 (A_i,A_{i+1})=(x,y) または (A_i,A_{i+1})=(y,x) を満たす整数 i\ (1\leq i\leq M-1) が存在する。

長さ M が最小であるような良い数列のうち、辞書順最小のものを求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 1\leq T\leq 99
• 2\leq N\leq 100
• 入力はすべて整数

入力例 1

2
3
2

出力例 1

1 2 3 1
1 2

N=3 のとき、例えば A=(1,2,1,3,2) は良い数列であることが以下のように確かめられます。

• (x,y)=(1,2) について、 (A_1,A_2)=(x,y) を満たす。
• (x,y)=(1,3) について、 (A_3,A_4)=(x,y) を満たす。
• (x,y)=(2,3) について、 (A_4,A_5)=(y,x) を満たす。

他にも良い数列として (1,2,3,1), (1,2,3,1,100), (3,1,2,3) などが挙げられます。一方、 (1,2,3),(1,2,1,3) は良い数列ではありません。

長さが 3 以下の良い数列は存在しないため、長さ 4 の良い数列のうち辞書順最小である (1,2,3,1) が求めるものです。

問題文

(1,2,\ldots,N) の順列を以下では単に順列と呼びます。

順列 P に対して、順列 \mathrm{NextPermutation} (P) を次で定めます。

• P=(N,N-1,\ldots,2,1) のとき (1,2,\ldots,N-1,N)
• そうでないとき、長さ N の順列全てを辞書順昇順に並べたときに P の次に来るもの

2 つの順列 P=(P_1, P_2, \ldots,P_N), Q=(Q_1, Q_2, \ldots, Q_N) が与えられます。

P が (1,2,\ldots, N-1,N) に一致するまで、次の操作を繰り返します。

• P を \mathrm{NextPermutation} (P) で、Q を \mathrm{NextPermutation} (Q) で置き換える。

最終的な Q を求めてください。

制約

• 2\leq N\leq 2\times 10^5
• (P_1, P_2, \ldots,P_N),(Q_1, Q_2, \ldots, Q_N) は (1,2,\ldots,N) の順列
• 入力はすべて整数

入力例 1

3
2 3 1
3 2 1

出力例 1

2 1 3

操作によって P,Q は以下のように変化します。

• P：(2,3,1)\to (3,1,2)\to (3,2,1)\to (1,2,3)
• Q：(3,2,1)\to (1,2,3)\to (1,3,2)\to (2,1,3)

入力例 2

4
4 2 1 3
2 1 3 4

出力例 2

2 4 1 3

操作によって P,Q は以下のように変化します。

• P：(4,2,1,3)\to (4,2,3,1)\to (4,3,1,2)\to (4,3,2,1)\to(1,2,3,4)
• Q：(2,1,3,4)\to(2,1,4,3)\to(2,3,1,4)\to(2,3,4,1)\to(2,4,1,3)

入力例 3

4
1 2 3 4
1 2 3 4

出力例 3

1 2 3 4

一度も操作を行いません。

問題文

正整数 L,R が与えられます。 L 以上 R 以下の正整数からなる空でない集合 S であって、 S のすべての要素を割り切るような正整数のうち最大のものが 1 であるようなものはいくつありますか？ 998244353 で割った余りを求めてください。

制約

• 1\leq L\leq R\leq 10^9
• 入力はすべて整数

入力例 1

1 4

出力例 1

11

S としてあり得るものは \lbrace1\rbrace,\lbrace1,2\rbrace,\lbrace1,3\rbrace,\lbrace1,4\rbrace,\lbrace2,3\rbrace,\lbrace3,4\rbrace,\lbrace1,2,3\rbrace,\lbrace1,2,4\rbrace,\lbrace1,3,4\rbrace,\lbrace2,3,4\rbrace,\lbrace1,2,3,4\rbrace です。

入力例 2

5 10

出力例 2

51

入力例 3

100 100

出力例 3

0

入力例 4

123456789 987654321

出力例 4

884200911

998244353 で割った余りを出力してください。

問題文

N 本の縦線からなるアミダクジがあります。
それぞれの縦線の長さは 2M+1 [\mathrm{cm}] であり、横線は以下の条件を満たす必要があります。

• 横線の端点となれるのは上から 1,2,\dots,2M [\mathrm{cm}] の高さのみであり、横線の両端点の高さは等しい
• 全ての横線は、隣り合う 2 つの縦線のみを繋ぐ
• 同じ高さにある横線は高々 1 本

初め、このアミダクジに M 本の横線がひかれています。 j\ (j=1,2,\dots,M) 本目の横線は、上から 2j [\mathrm{cm}] の位置にひかれており、左から a_j 本目の縦線と a_j+1 本目の縦線を結んでいます。

このアミダクジに以下の操作を任意の回数 ( 0 回も可) 行う事が出来ます。

• まだ横線のひかれていない高さ h 及び、1 以上 N-1 以下の整数 b を選ぶ。
  上から h [\mathrm{cm}] の位置に左から b 本目の縦線と b+1 本目の縦線を結ぶ横線を追加する。

すべての i=1,2,\dots,N に対して左から i 本目の縦線からクジを辿り始めると結果が左から i 本目となるアミダクジを 「恒等的なアミダクジ」 と呼ぶとき、与えられたアミダクジを恒等的なアミダクジにするために必要な最小の操作回数を求めてください。
また、最小の操作回数を達成する操作の方法を 1 つ示してください。
この制約の元、恒等的なアミダクジにする操作方法が常に存在することが示せます。

制約

• 2 \leq N \leq 2\times10^5
• 1\leq M\leq 2\times10^5
• 1 \leq a_j < N\ (j=1,2,\dots,M)
• 入力はすべて整数

入力例 1

3 2
1 2

出力例 1

2
1 1
3 2

他にも、

2
1 2
3 1

を出力しても正解となります。

入力例 2

5 4
2 3 4 1

出力例 2

4
1 2
3 3
5 4
7 1

入力例 3

100000 4
1 2 2 1

出力例 3

0

操作をしなくても恒等的なアミダクジになっている場合もあります。

問題文

長さ N の正整数列 (A_1,A_2,\dots,A_N) が与えられます。 M=\max\,\{A_i\mid 1\leq i\leq N\} とし、区間 (0,M] を K 個の区間に分割します。すなわち、非負実数 m_i \, (i=0,1,\dots,K) を 0=m_0<m_1<m_2<\dots<m_{K-1}<m_K=M を満たすように選んで (0,M]=(m_0,m_1]\cup(m_1,m_2]\cup\dots\cup(m_{Kー1},m_{K}] とします。

区切り方を適切に定めたとき、 \[ \displaystyle \sum_{i=1}^{K} m_i \times (A_j \in (m_{i-1}, m_i]\text{となる}j\text{の個数}) \] の最小値を求めてください。答えは必ず整数になることが証明できます。

制約

• 1 \leq N \leq 10^5
• 1 \leq K \leq 10^5
• 1 \leq A_i \leq 10^5 \, (i=1,2,\dots,N)
• 入力はすべて整数

入力例 1

4 2
3 7 4 5

出力例 1

22

例えば、 (0,7]=(0,4]\cup(4,7] と分割すると、求める値は 4 \times 2 + 7 \times 2 = 22 となり、これが最小です。

入力例 2

19 4
3279 97197 36049 32099 29257 18290 96531 13435 88697 97081 71483 11396 77398 55303 4166 3906 12281 28658 30496

出力例 2

917886

問題文

この問題はインタラクティブな問題です。

(1,2,\cdots,N) の順列を単に長さ N の順列と呼ぶことにします。
長さ N の順列 P=(P_1, P_2, \cdots, P_N) があります。
また、長さ N の 2 つの順列 P,Q に対して \mathrm{dist}(P,Q) を以下のように定義します。

• P を Q に一致させるために必要な隣接要素の交換回数の最小値

あなたは次のような質問を 500 回 まで行うことができます。

• 長さ N の順列 Q を 1 つ指定する。以下の規則でジャッジから文字が与えられる。

  • 質問が 1 回目であれば 「=」を出力する。
  • 前回の質問であなたが出力した順列を Q_1, 今回の質問であなたが出力した順列を Q_2 とする。
    \mathrm{dist}(P,Q_1) と \mathrm{dist}(P,Q_2) の大小関係に応じて「+」「-」「=」のいずれかを出力する。具体的には以下の通りである。
    • \mathrm{dist}(P,Q_1) < \mathrm{dist}(P,Q_2) のとき「+」
    • \mathrm{dist}(P,Q_1) > \mathrm{dist}(P,Q_2) のとき「-」
    • \mathrm{dist}(P,Q_1) = \mathrm{dist}(P,Q_2) のとき「=」

長さ N の順列 P を求めてください。
ただし、回答は質問回数に含めません。

制約

• 2 \leq N \leq 100
• N は整数
• P はプログラムとジャッジの対話の開始前に決定される

注意点

• 出力を行うたびに標準出力をflushせよ。

入出力例

以下では N=4, P= (1,2,3,4) の場合の対話例です。

問題文

根付き木 S に対して、根付き木 f(S) を、S に対して次の操作を行ったものとします。

• 木 S の葉をすべて S 自身で置き換える

根付き木 S に対して、木の無限列 (S_1, S_2, \dots) を次のようにして定義します。

• S_1 := S
• S_i := f(S_{i-1}) \quad (i > 1)

無限木 S_{\infty}:= \displaystyle\lim_{n\to\infty} S_n を S から誘導される fractal tree と呼びます。

K 個の根付き木 T_1, T_2, \dots, T_K が与えられます。 T_i\,(i=1,2,\dots,K) は、以下の条件をみたす根付き木です。

• 頂点数は N_i \geq 2
• 頂点には 1,2,\dots,N_i の番号が付けられている
• 根は頂点 1 である
• j=2,3,\dots,N_i について、頂点 j の親は頂点 p_{i,j} である

各 (i,j) \, (i,j=1,2,\dots,K) について、 T_i,\,T_j からそれぞれ誘導される fractal tree (T_i)_\infty と (T_j)_\infty が同型か判定してください。

制約

• 2 \leq K \leq 1000
• 2 \leq N_i \leq 5 \times 10^4 \quad (1 \leq i \leq K)
• \displaystyle\sum_{i=1}^K N_i \leq 10^5
• 1 \leq p_{i,j} < j \quad (1 \leq i \leq K,\,2\leq j \leq N_i)
• 入力はすべて整数

入力例 1

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

出力例 1

1100
1100
0011
0011

与えられる木は以下の通りです。

これらの木に 1 回操作を施した木は以下の通りです。

問題文

2 \times 2 行列 A = \begin{pmatrix} a & b \\ c & d \end{pmatrix} が与えられます。A の要素は非負整数です。

あおばさんとひろせさんがこの行列を用いてゲームをします。あおばさんが先手で、交互に以下の行動をします。

• A の行または列を一つ選んで、選んだ行または列の各要素から同じ正整数を引く。このとき、A の要素が負になってはいけない。

行動ができなくなった方の負けで、負けなかった方が勝ちです。両者がそれぞれ自身が勝つために最適な戦略をとる場合に、どちらが勝つかを判定してください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 1 \leq T \leq 1000
• 0 \leq a, b, c, d \leq 10^9
• 入力はすべて整数

入力例 1

4
1 3 5 0
3 0 0 7
3 1 4 1
5 9 2 5

出力例 1

First
Second
First
Second

1 ケース目で与えられる行列は \begin{pmatrix} 1 & 3 \\ 5 & 0 \end{pmatrix} です。先手が 1 行目から 1 を引くことで行列は \begin{pmatrix} 0 & 2 \\ 5 & 0 \end{pmatrix} となり、後手は操作が行えないので先手の勝ちです。

問題文

S_{n,m} を n 文字の 0 と m 文字の 1 からなる長さ n+m の文字列全体の集合とします。

s_1, s_2\in S_{n,m} に対して、 s_1, s_2 の距離 d(s_1, s_2) を「隣り合った 2 文字を入れ替える操作によって文字列 s_1 を文字列 s_2 に並び替えるのに必要な最小の操作回数」と定義します。

また、 s_1, s_2\in S_{n,m} に対して、f(s_1,s_2) を次で定めます。

• d(s_1,t)=d(s_2,t) となる文字列 t\in S_{n,m} が存在するとき、そのような文字列の中で辞書順最小のものを返す。そのような文字列が存在しないときは -1 を返す。

正整数 n,m と文字列 T \in S_{n,m} が与えられます。 f(s_1,s_2)=T となるような文字列の組 (s_1,s_2)\ (s_1, s_2\in S_{n,m}) はいくつありますか？ 998244353 で割った余りを求めてください。

制約

• 1\leq n,m\leq 30
• n,m は整数
• T\in S_{n,m}

入力例 1

2 2
0101

出力例 1

4

(s_1,s_2)=( 0011 , 0110 ),(0011 , 1001 ),( 0110 , 0011 ),( 1001 , 0011 ) が条件を満たします。

例えば、 (s_1,s_2)=( 0011 , 0110 ) について、d(s_1, t)=d(s_2, t) を満たす t\in S_{2,2} は 0101 と 1001 がありますが、このうち辞書順で小さいものは 0101 であるため、f(s_1, s_2)= 0101 です。

入力例 2

4 1
00100

出力例 2

4

(s_1,s_2)=( 00001 , 10000 ),(00010 , 01000 ),( 01000 , 00010 ),( 10000 , 00001 ) が条件を満たします。

入力例 3

3 3
111000

出力例 3

0

入力例 4

6 4
0001111000

出力例 4

1254