問題文

パ研合宿 2021 の参加者数を「合宿の一日目が開始した時点でパ研合宿 2021 の Discord サーバーに入っている人の数」と定義したとき、その値はいくらになりますか？

出力例

51

今年のパ研合宿は大所帯です。

原案: penguinman

問題文

パケンくんは、パソコン力を高めたいです。

ある日、パケンくんは問題を解くことでパソコン力を得られることに気づきました。

具体的には、難易度 x の問題を解くと、x^2 \times b のパソコン力が得られます。

2 整数 a,b が与えられるので、パケンくんが難易度 a の問題を解いたときにいくつのパソコン力が得られるかを求め、出力してください。

制約

• 1 \leq a,b \leq 13
• 入力される値は全て整数

入力例 1

3 4

出力例 1

36

3^2 \times 4 = 36 です。

原案: primenumber_zz

問題文

パ研くんは 2 日間にわたってプログラミングコンテストを開催しました。 1 日目のコンテストには N 人が参加し、 2 日目のコンテストには M 人が参加しました。

コンテストの参加者にはそれぞれ ID と呼ばれる整数が割り当てられていました。 1 日目の参加者の ID は順に A_1, A_2, \ldots, A_N で、 2 日目の参加者の ID は順に B_1, B_2, \ldots, B_M でした。異なる人に同じ ID が割り当てられたことはありません。

パ研くんは次の条件を満たす人の ID の一覧を欲しがっています。

• 1 日目のコンテストには参加しなかったが、 2 日目のコンテストには参加した。

パ研くんのかわりに条件を満たす人の ID を列挙してください。

制約

• 1 \leq N \leq 3000
• 1 \leq M \leq 3000
• 1 \leq A_i \leq 3000
• 1 \leq B_i \leq 3000
• i \neq j \implies A_i \neq A_j
• i \neq j \implies B_i \neq B_j
• 入力される値は全て整数

入力例 1

3 4
1 3 4
6 8 3 1

出力例 1

2
6
8

ID が 6 の人と 8 の人は 1 日目のコンテストには参加しませんでしたが、 2 日目のコンテストには参加しました。

ID はどの順番で出力してもよいので、次のような出力も正答となります。

2
8
6

入力例 2

4 3
8 4 2 1
1 4 2

出力例 2

0

条件を満たす人が存在しないこともあります。

入力例 3

3 2
1234 312 999
888 519

出力例 3

2
519
888

入力例 4

10 8
14 9 3 8 11 18 20 12 16 17
6 4 5 18 11 14 19 20

出力例 4

4
4
5
6
19

原案: Forested

問題文

筑駒 72 期 高校 1 年 3 学期の漢文の期末試験では、表紙に「選択問題の正答はすべて同じ選択肢で統一しています。この注意事項に気づいても試験終了までは声に出さずに秘密裡にすること。」という注意書きがなされていました。

仮にこの試験が N 問の選択問題のみからなり、各問題は 1 から M までの選択肢から 1 つを選ばせるような出題形式になっていたとしましょう。

この注意書きに気づかなかったペンギンくんは、各 i\ (1 \leq i \leq N) について i 問目の答えを A_i と書いてしまいました。

ペンギンくんの正答数として考えられる値の最小値および最大値は、それぞれいくらになりますか？

制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 10^9
• 1 \leq A_i \leq M
• 入力は全て整数

入力例 1

3 2
1 1 2

出力例 1

1 2

試験におけるすべての問題の答えが 1 であったとき、ペンギンくんの正答数は 2 となります。

試験におけるすべての問題の答えが 2 であったとき、ペンギンくんの正答数は 1 となります。

よって、ペンギンくんの正答数として考えられる値の最小値と最大値は、それぞれ 1、2 となります。

入力例 2

4 5
5 1 1 5

出力例 2

0 2

試験におけるすべての問題の答えが 2 であったとき、ペンギンくんの正答数は 0 となり、これは考えられる値の最小値です。

試験におけるすべての問題の答えが 1 であったとき、ペンギンくんの正答数は 2 となり、これは考えられる値の最大値です。

原案: penguinman

問題文

正整数 N,M が与えられます。すべての要素が 1 以上 M 以下である長さ N の正整数列 a であって、以下の条件を満たすものの個数を 998244353 で割った余りを求めてください。

• a の長さ 2 以上の連続部分列であって、回文であるようなものが存在しない。

制約

• 2 \le N \le 10^{12}
• 1 \le M \le 10^{12}
• 入力は全て整数

入力例 1

2 2

出力例 1

2

a=(1,2),(2,1) の時条件を満たします。

入力例 2

3 3

出力例 2

6

入力例 3

314 159

出力例 3

809839613

998244353 で割った余りを求めることをお忘れなく。

原案: turtle0123__

問題文

正整数 N が与えられます。

\dfrac{a}{b} < \dfrac{c}{d} < \dfrac{e}{f} を満たす整数の組 (a,b,c,d,e,f)\ (1 \le a,b,c,d,e,f \le N) のうち、\dfrac{e}{f}-\dfrac{a}{b} が最小になるものを一つ構築してください。

この問題の制約下で、\dfrac{a}{b} < \dfrac{c}{d} < \dfrac{e}{f} を満たす整数の組 (a,b,c,d,e,f) は必ず存在します。

制約

• 2 \le N \le 10^9
• 入力は全て整数

入力例 1

2

出力例 1

1 2 1 1 2 1

\dfrac{1}{2}<\dfrac{1}{1}<\dfrac{2}{1} です。 1 2 2 2 2 1 と答えても正解となります。

入力例 2

3

出力例 2

1 3 1 2 2 3

原案: turtle0123__

問題文

パ研部長のぺんぎんくんは、パ研の部室を増やしたいと思いました。

ぺんぎんくんのいる学校には N 個の部屋があり、部屋 1 から部屋 N までの番号が付けられています。

また、M 本の廊下があり、i 番目の廊下は部屋 U_i と部屋 V_i を双方向に結んでいます。これらの廊下を使って移動することで、どの部屋からどの部屋にも行くことができます。

現在、パ研の部室は部屋 1 のみです。ぺんぎんくんは今日を 1 日目として、 1 日 1 回以下の操作を行うことで、N-1 日目に全ての部屋がパ研の部室となっているようにします。

• 現時点でパ研の部室である部屋のいずれかと直接廊下で結ばれていてかつ現時点ではパ研の部室ではない部屋を 1 つ選び、新しくパ研の部室とする。

i 日目に部屋 j を新しくパ研の部室にしたとき、ぺんぎんくんの嬉しさは A_{i,j} 上昇します。はじめ、ぺんぎんくんの嬉しさは 0 です。

N-1 日目の操作が終わった時点でのぺんぎんくんの嬉しさとして考えられる値の最大値を求め、出力してください。

制約

• 2 \leq N \leq 15
• 1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq U_i < V_i \leq N
• (U_i,V_i) \neq (U_j,V_j)\ (i \neq j)
• 1 \leq A_{i,j} \leq 10^5\ (2 \leq j \leq N),\ A_{i,j} = 0\ (j = 1)
• どの部屋からどの部屋へも 0 本以上の廊下を経由して移動することができる
• 入力は全て整数

入力例 1

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

出力例 1

7

1 日目に部屋 2 を部室とし、2 日目に部屋 3 を部室とすると、嬉しさは A_{1,2} + A_{2,3} = 5

1 日目に部屋 3 を部室とし、2 日目に部屋 2 を部室とすると、嬉しさは A_{1,3} + A_{2,2} = 7

となるので、答えとして 7 を出力してください。

入力例 2

4 5
1 3
2 3
3 4
2 4
1 4
0 1 2 3
0 31 41 59
0 1 6 82

出力例 2

115

原案: primenumber_zz

問題文

プラプライムくんは、以下の条件をすべて満たす整数 N が存在するか気になっています。

• 1 \leq N \leq 10^{18}
• N は与えられる M 個の情報に矛盾しない。i 個目の情報は素数 P_i と正整数 S_i の組 (P_i,S_i) からなり、N! は P_i^{S_i} で割り切れるが、P_i^{S_i+1} で割り切れないことを表す。

プラプライムくんのために条件を満たす N を 1 つ見つけてあげるか、あるいはそのような N が存在しないことを教えてあげてください。

制約

• 1 \leq M \leq 10^5
• 1 \leq P_i \leq 10^9
• 1 \leq S_i \leq 10^{18}
• P_i は素数
• 入力は全て整数

入力例 1

2
2 3
5 1

出力例 1

5

5! = 120 は 2^3 = 8 で割り切れますが、2^4 = 16 では割り切れません。また、同様に 5^1 = 5 で割り切れますが、5^2 = 25 では割り切れません。

よって 5 は問題文中の条件を満たします。

入力例 2

3
2 4
5 1
3 5

出力例 2

-1

条件を満たす整数が存在しない場合は、-1 を出力してください。

原案: primenumber_zz

問題文

長さ N-1 の正整数 A=(A_2,A_3,\ldots,A_N),B=(B_2,B_3,\ldots,B_N) が与えられます。(添字が 2 から始まることに注意してください)

数列 A に対して以下の操作を 10^6 回以下行って A=B にする方法があるか判定し、あるならば 1 つ構築してください。

• 整数 i\ (2 \le i) とその倍数 j を選び、A_i の値と A_j の値を交換する。なお、このとき i=j であってもよい。

制約

• 2 \le N \le 50000
• 1 \le A_i,B_i \le 50000\ (2 \le i \le N)
• 入力は全て整数

入力例 1

4
3 2 4
4 2 3

出力例 1

1
2 4

入力例 2

2
3
4

出力例 2

-1

入力例 3

6
4 1 3 2 5
1 5 4 2 3

出力例 3

3
3 6
2 4
2 6

原案: turtle0123__

問題文

正整数 N,M と長さ N の整数列 T=(T_1,T_2,\ldots,T_N),A=(A_1,A_2,\ldots,A_N) が与えられます。

すべての要素が 1 以上 M 以下である長さ N+1 の正整数列 b=(b_1,b_2,\ldots,b_{N+1}) であって、すべての i\ (1 \le i \le N) について以下の条件を満たすものの個数を 998244353 で割った余りを求めてください。

• T_i=0 のとき、 \min(b_i,b_{i+1})=A_i
• T_i=1 のとき、 \max(b_i,b_{i+1})=A_i

制約

• 1 \le N, M \le 2 \times 10^5
• T_i \in \{0, 1 \}
• 1 \le A_i \le M
• 入力は全て整数

入力例 1

2 2
0 0
1 2

出力例 1

1

b=(1,2,2) の時条件を満たします。

入力例 2

2 4
0 1
1 2

出力例 2

6

入力例 3

15 509
1 0 1 1 1 1 0 1 1 1 1 1 1 0 0
367 241 241 160 160 156 156 459 395 288 288 408 505 270 270

出力例 3

684062245

998244353 で割った余りを求めることをお忘れなく。

原案: turtle0123__

問題文

かめ君は、文字列で遊ぶのが好きです。今日は、空文字列 s を用意し、以下の操作を N 回行いました。

• s を文字列 l,r に分割する。 s を l\ + () +\ r に置き換える。

N 回の操作後の s の値が T として与えられるので、 操作の方法として考えられるものの個数を 998244353 で割った余りを求めてください。

ただし、ある正整数 k\ (1 \le k \le N) が存在して k 回目の操作における (l,r) の組が異なるとき、またその時に限り 2 つの操作の方法を異なるとみなします。

また、かめ君は嘘をつかないので、必ず s=T となる操作の方法が 1 つは存在するような T のみが与えられます。

制約

• 1 \le N \le 10^5
• T は (, ) からなる長さ 2N の文字列
• 適切な操作をすることで、必ず s=T にすることが可能

入力例 1

3
(())()

出力例 1

3

以下のような操作が考えられます。

1 回目、 l,r を空文字列 とする。 s= () となる。

2 回目、 l= () ,r を空文字列 とする。 s= ()() となる。

3 回目、 l= ( ,r= )() とする。 s= (())() となる。

入力例 2

1
()

出力例 2

1

入力例 3

7
(()(()(())()))

出力例 3

72

原案: turtle0123__

問題文

N 頂点 M 辺の単純連結重み付き無向グラフが与えられます。頂点には 1 から N までの番号が、辺には 1 から M までの番号が振られています。辺 i は頂点 U_i と頂点 V_i を結び、重みは W_i です。辺の重みは全て互いに異なることが保証されます。

頂点 1 から頂点 N への、頂点の重複を許した道を考えます。通った辺の重みを順に並べた数列を C = (C_1, C_2, \ldots, C_k) として、次の条件を満たす道をジグザグ道と定義します。

• C_1 < C_2 > C_3 < \cdots または C_1 > C_2 < C_3 > \cdots である。つまり、次の条件のいずれかを満たす。
  • 任意の整数 i \, (1 \leq i \leq k - 1) について、 i が奇数ならば C_i < C_{i+1} であり、 i が偶数ならば C_i > C_{i+1} である。
  • 任意の整数 i \, (1 \leq i \leq k - 1) について、 i が奇数ならば C_i > C_{i+1} であり、 i が偶数ならば C_i < C_{i+1} である。

ジグザグ道は存在するでしょうか？存在するならば、通る辺の重みの総和の最小値も求めてください。

制約

• 2 \leq N \leq 10^5
• N - 1 \leq M \leq \min \left( \cfrac{N(N-1)}{2}, 10^5 \right)
• 1 \leq U_i < V_i \leq N
• 1 \leq W_i \leq 10^9
• (U_i, V_i) \neq (U_j, V_j) \, (i \neq j)
• W_i \neq W_j \, (i \neq j)
• 入力で与えられるグラフは単純かつ連結
• 入力は全て整数

入力例 1

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

出力例 1

14

辺 1, 5, 3, 4 の順に通ると C = (4, 3, 6, 1) となり、ジグザグ道の条件を満たします。このとき重みの総和は 14 です。

辺 1, 5, 2 の順に通る道は C = (4, 3, 2) となりジグザグ道ではありません。

入力例 2

4 3
1 2 4
2 3 6
3 4 8

出力例 2

-1

入力例 3

7 12
2 5 657831697
5 6 925940778
1 2 749029915
2 4 237755672
3 6 60634766
6 7 65418621
1 4 194639839
4 7 411656898
3 7 367905753
3 4 241675120
1 6 858592389
2 6 571202751

出力例 3

562368346

原案: primenumber_zz

問題文

正の整数 N が与えられます。Natsubi くんは、空の数列 Q を用意したうえで、(1,2,\dots,N) を並び替えた数列 P=(P_1, P_2, \dots, P_N) を自由に選んで、以下の一連の操作を N 回行います。

1. P の先頭の要素を x として、Q の先頭または末尾に x を追加する。
2. P から x を削除する。

Natsubi くんは、最終的な Q の転倒数が最小となるように適切に操作を行います。

P として考えられるものは N! 通りありますが、それらすべてについて操作後の Q の転倒数の最小値を求め、その総和を 998244353 で割ったあまりを出力してください。

制約

• 1 \leq N \leq 3 \times 10^5
• 入力は全て整数

入力例 1

4

出力例 1

20

例えば、P=(3,2,1,4) のとき、適切に操作を行うことで Q=(1,2,3,4) とすることができ、転倒数は 0 となります。

他の P についても同様に計算すると、答えは 20 であることが分かります。

入力例 2

220328

出力例 2

192799865

原案: NatsubiSogan

問題文

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

整数 k と N 次の整数係数多項式 f(x)=a_Nx^N+a_{N-1}x^{N-1}+\ldots+a_0 、 M 次の整数係数多項式 g(x)=b_Mx^M+b_{M-1}x^{M-1}+\ldots+b_0 が与えられます。 f(k) と g(k) の大小関係を求めてください。

制約

• 1 \le T \le 10^5
• 0 \le N, M \le 10^5
• |a_i|, |b_j|, |k| \le 10^5
• a_N, b_M \neq 0
• 1 つの入力で与えられる N,M の総和はそれぞれ 10^5 を超えない
• 入力はすべて整数

入力例 1

3
2 1 3
2 0 1
4 5
0 0 0
2
2
5 7 -89401
-79604 56304 -25588 -4414 73961 28352
-6628 -12831 6978 373 -36054 82166 30928 50750

出力例 1

>
=
<

1 ケース目について、 f(x)=2x^2+1,g(x)=4x+5 ですから、 f(3)=19,g(3)=17 より f(3)>g(3) です。

原案: turtle0123__

問題文

文字列 S が与えられます。 S[i:j] で S の i 文字目から j 文字目までを取り出した文字列を表すことにします。

文字列 T が次の条件を全て満たすとき、 T は良い文字列であると定義します。

• 1 \leq |T| \leq |S|
• S[i:i+|T|-1] = T を満たす整数 i はちょうど 1 つだけ存在する

例えば S が abcbabc のとき、 cb や abcb 、 abcbabc は良い文字列ですが、 abc や zyx は良い文字列ではありません。

Q 個のクエリが与えられるので処理してください。 i 番目のクエリでは 1 \leq L_i \leq R_i \leq |S| を満たす整数 L_i, R_i が与えられるので、次の問題の答えを出力してください。

• 2 つの整数 l, r であって、 1 \leq l \leq L_i と R_i \leq r \leq |S| を満たし、かつ S[l:r] が良い文字列であるようなものを考える。 r-l+1 の最小値はいくつか？

制約

• S は英小文字からなる
• 1 \leq |S| \leq 2 \cdot 10^5
• 1 \leq Q \leq 2 \cdot 10^5
• 1 \leq L_i \leq R_i \leq |S| \, (1 \leq i \leq Q)

入力例 1

abcbabc
5
2 3
2 5
1 7
4 4
6 6

出力例 1

3
4
7
2
3

1 番目のクエリでは、 l=2, r=4 とすると r-l+1=3 となり、これが最小です。 bc は良い文字列ではないので、 l=2, r=3 とすることはできません。

2 番目のクエリでは、 l=2, r=5 とすると r-l+1=4 となり、これが最小です。

3 番目のクエリでは、 l=1, r=7 とすると r-l+1=7 となり、これが最小です。一般に S そのものは良い文字列であることに注意してください。

入力例 2

yyxxzzyyxx
5
3 3
1 1
10 10
5 5
7 7

出力例 2

3
5
5
2
2

入力例 3

qprrrrrpprqrrppq
20
7 8
6 8
4 7
7 12
6 7
5 5
6 8
4 6
4 4
2 3
7 11
8 9
6 7
11 12
11 15
5 6
4 5
13 13
9 13
5 7

出力例 3

4
4
5
6
4
4
4
5
3
3
5
3
4
2
5
4
4
3
5
4

原案: Forested

問題文

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

正整数 A,M が与えられます。 A^k \equiv k \pmod M を満たす非負整数 k\ (k < M \times \varphi (M)) の個数を求め(ans とします)、条件を満たす k を \min(ans,1000) 個構築してください。

ただし、 \varphi(M) はオイラーのファイ関数を表します。

制約

• 1 \le T \le 100
• 1 \leq A,M \leq 10^9
• 入力は全て整数

入力例 1

1
2 4

出力例 1

1
4

2^4\equiv 4 \pmod 4 です。

原案: turtle0123__