長さ $N$ の整数列 $A=(A_1,A_2,...,A_N)$ が与えられます． $A$ の連続するとは限らない，長さが $2$ 以上である部分列 $A'=(A'_1,A'_2,...A'_k)$ のうち以下の条件を満たすものの個数を求め， $998244353$ で割ったあまりを求めてください．

条件： $A'_1 \leq A'_k$

制約

・ $2 \leq N \leq 3 \times 10 ^ 5$

・ $1 \leq A_i \leq 10 ^ 9$

Coprime Present

問題リンク

問題概要

$A$ 以上 $B$ 以下の整数が書かれたカードをそれぞれ $1$ 枚ずつ，計 $B - A +1$ 枚持っています．以下の条件を満たすようなカードの選び方(選ぶ枚数は $0$ 枚でもよい)は何通りありますか．

条件：選ばれたカードのどの相異なる $2$ 枚に書かれた数も互いに素である．

制約

・ $1 \leq A \leq B \leq 10 ^ {18}$

・ $B - A \leq 72$

GCD on Blackboard

問題リンク

問題概要

$N$ 個の整数 $A_1,A_2,...A_N$ のうち $1$ つ選んで好きな正整数に書き換えます．書き換えた後の $N$ 個の整数の最大公約数の最大値を求めてください．

制約

・ $2 \leq N \leq 10 ^ 5$

・ $1 \leq A_i \leq 10 ^ 9$

2017-like Number

問題リンク

問題概要

以下の条件を満たす奇数を2017に似た数とします．

条件： $N$ も $(N+1) \div 2$ も素数である

ここで以下の問に $Q$ 回答えてください．問 $i$ の形式は以下の通りです．

問 $i$ ： $l_i,r_i$ が与えられるので， $l_i$ 以上 $r_i$ 以下の2017に似た数の個数を求めてください

制約

・ $1 \leq Q \leq 10 ^ 5$

・ $1 \leq l_i \leq r_i \leq 10 ^ 5$

joisino's travel

問題リンク

問題概要

$N$ 頂点 $M$ 辺の無向グラフが与えられます．辺 $i$ は頂点 $A_i$ と頂点 $B_i$ を結んでいて，その距離は $C_i$ です．あなたは頂点 $r_1,r_2,...r_R$ を訪れることになりました．訪れる頂点の順番を適切に選んだときその移動距離の最小値はどうなるでしょうか．

制約

・ $2 \leq N \leq 200$

・ $1 \leq M \leq N \times (N-1) /2$

・ $1 \leq C_i \leq 10 ^ 5$

Easy

・ $2 \leq R \leq \mathbf{min}(8,N)$

Hard

・ $2 \leq R \leq \mathbf{min}(13,N)$

・与えられるグラフは多重辺や自己ループを持たず，どの頂点間も辺を経由して移動することができる

Anything Goes to Zero

問題リンク

問題概要

$\mathbf{popcount}(n)$ を $n$ を $2$ 進数表記したときの1の個数とします．たとえば $\mathbf{popcount}(3)=2$ ， $\mathbf{popcount}(0)=0$ です．

$f(n)$ を「 $n$ を $\mathbf{popcount}(n)$ で割ったあまりに置き換える」という操作を繰り返した際に $n$ が $0$ になるまでの操作回数とします．

以下は $n=7$ の例で， $2$ 回の操作で $n$ が $0$ になります．

・ $\mathbf{popcount}(7)=3$ なので $7$ を $3$ で割ったあまりである $1$ に置き換える．

・ $\mathbf{popcount}(1)=1$ なので $1$ を $1$ で割ったあまりである $0$ に置き換える．

$2$ 進数表記で $N$ 桁の整数 $X$ が与えられます． $1 \leq i \leq N$ を満たす整数 $i$ について， $X$ の上から $i$ 桁目のビットを反転した整数を $X_i$ とします． $f(X_1),f(X_2),...,f(X_N)$ をそれぞれ求めてください．

制約

・ $1 \leq N \leq 2 \times 10 ^ 5$

・ $X$ は $2$ 進数表記で $N$ 桁の(先頭が $1$ とは限らない)整数

Product of Arithmetic Progression

問題リンク

問題概要

以下の問に $Q$ 回答えてください．問 $i$ の形式は以下の通りです．

問 $i$ ：初項 $x_i$ ，公差 $d_i$ ，項数 $n_i$ の等差数列の総積，つまり

$\displaystyle \prod_{k=1}^{n_i} (x_i+d_i (k-1))$

を $10 ^ 6 +3$ で割ったあまりを求めてください．

制約

・ $1 \leq Q \leq 10 ^5$

・ $0 \leq x_i ,d_i \leq 10^ 6 + 2$

・ $1 \leq n_i \leq 10 ^ 9$

Balanced Neighbors

問題リンク

問題概要

頂点に $1$ から $N$ の番号がついた $N$ 頂点の単純かつ連結である無向グラフであって，以下の条件を満たすものを $1$ つ構成してください．

条件：ある整数 $S$ が存在して，任意の頂点についてその頂点に隣接する頂点の番号の値の和は $S$ となる

条件を満たすグラフが必ず存在することが証明できます．

制約

・ $3 \leq N \leq 100$

01 Matrix

問題リンク

問題概要

$H$ 行 $W$ 列からなるマス目を $0$ か $1$ で埋めることを考えます．以下の条件を満たす埋め方を $1$ つ示してください．不可能な場合はそれを報告してください．

条件

・どの行についてもその行に含まれる $0$ の個数と $1$ の個数のうち小さいほうが $A$ である．

・どの行についてもその列に含まれる $0$ の個数と $1$ の個数のうち小さいほうが $B$ である．

制約

・ $1 \leq H,W \leq 1000$

・ $0 \leq A,B$

・ $2 \times A \leq W$

・ $2 \times B \leq H$

GCD Sequence

問題リンク

問題概要

正整数の集合 $S = \left\{ a_1, a_2, ... a_N \right\}$ が以下の条件を満たす場合特別な集合であると言われます．

条件：どの $1 \leq i \leq N$ についても $a_i$ と $S$ のその他の要素の和の最大公約数は $1$ ではない．

要素数 $N$ の特別な集合であって， $\mathbf{gcd}(a_1, a_2, ... a_N) =1$ であり， $\mathbf{max}(a_1, a_2, ... a_N) \leq 30000$ であるものを $1$ つ求めてください．この問題の制約下では条件を満たすものが少なくとも1つは存在することが保証されます．

制約

・ $3 \leq N \leq 20000$

MAD TEAM

問題リンク

問題概要

$N$ 人のメンバーがいて，それぞれのメンバーは $5$ つのステータスがあります． $i$ 人目の $j$ 個目のステータスの値は $S_{i,j}$ です．便宜上 $i$ 人目のメンバーの番号を $i$ とします．

$N$ 人の中から $3$ 人を選んでチームを組みます． $3$ 人のメンバーの番号が $x_1,x_2,x_3$ であったとき，そのチームの総合力は以下で計算されます．

チームの総合力 $= {\underset{1 \leq j \leq 5}{\mathbf{min}}} \left ( {\underset{1 \leq i \leq 3}{\mathbf{max}}(S_{{x_i},j})} \right)$

このとき，チームの総合力としてあり得る最大の値を求めてください．

制約

・ $3 \leq N \leq 3000$

・ $1 \leq S_{i,j} \leq 10 ^ 9$

Equal Weight

問題リンク

問題概要

$0$ から $N-1$ までの番号がついた $N$ 個のシャリと， $0$ から $M-1$ までの番号がついた $M$ 個のネタがあります．シャリ $i$ の重さは $A_i$ で，ネタ $j$ の重さは $B_j$ です．

あなたは寿司の握りを $2$ つ作りたいです． $1$ つの握りはちょうど $1$ つのシャリとネタを組み合わせ作ることで作られます．

あなたは $2$ つの握りの重さが等しくなるようにしたいです．これが可能かどうか判定し，可能ならばその作り方を $1$ つ示してください．なお，同じシャリやネタを $2$ 回使うことはできません．

制約

・ $2 \leq N,M \leq 2 \times 10 ^ 5$

・ $1 \leq A_i \leq 10 ^ 6$

・ $A_i \neq A_j (i \neq j)$

・ $1 \leq B_i \leq 10 ^6$

・ $B_i \neq B_j (i \neq j)$

Built?

問題リンク

問題概要

平面上に $N$ 個の街があり， $i$ 個目の街は座標 $(x_i,y_i)$ にあります．同じ座標に複数の街がある場合もあります．座標 $(a,b)$ にある街と座標 $(c,d)$ にある街の間に道を造るのには $\mathbf{min}(|a-c|,|b-d|)$ 円かかります．街と街の間以外に道を造ることはできません．

任意の $2$ つの街の間を，道を何本か通って行き来できるようにするためには最低で何円必要でしょうか．

制約

・ $2 \leq N \leq 10 ^ 5$

・ $0 \leq x_i,y_i \leq 10 ^ 9$

Keep Graph Connected

問題リンク

問題概要

$1$ から $N$ の番号が付いた $N$ 個の頂点と $1$ から $M$ の番号が付いた $M$ 本の辺からなる連結な無向グラフが与えられます．このグラフには多重辺が存在するかもしれませんが，自己ループはありません．

このグラフのそれぞれの辺には $1$ 以上 $N$ 以下の整数で表されるラベルがついています．辺 $i$ にはラベル $c_i$ がついており，頂点 $u_i,v_i$ を双方向につなぐ辺です．

あなたはそれぞれの頂点に $1$ 以上 $N$ 以下の整数を書き込んだのち(頂点に書き込まれた整数に重複があっても構いません)，以下の条件を満たす辺のみを残してそれ以外の辺を取り除くことにしました．

条件：辺の両端の頂点に書き込まれた整数を $x,y$ として， $x,y$ のいずれか一方のみが辺についたラベルと等しい

上記の条件を満たさない辺を取り除いたあとのグラフも連結のままであるような頂点への整数の書き込み方が存在するかどうか調べ，存在するならその一例を，存在しないならば存在しないことを報告してください．

制約

・ $2 \leq N \leq 10 ^ 5$

・ $N-1 \leq M \leq 2 \times 10 ^ 5$

・ $1 \leq u_i,v_i,c_i \leq N$

・与えられるグラフは連結

・与えられるグラフに自己ループはない

Packing Potatoes

問題リンク

問題概要

ベルトコンベアに載って $10^{100}$ 個のじゃがいもが $1$ 個ずつ流れてきます．流れてくるじゃがいもの重さは長さ $N$ の数列 $W=(W_0,W_1,...,W_{N-1})$ で表され， $i (1 \leq i \leq 10 ^ {100})$ 番目に流れてくるじゃがいもの重さは $W_{(i-1) \mathbf{mod} N}$ です．ここで， $(i-1) \mathbf{mod} N$ は $i-1$ を $N$ で割ったあまりを表します．