No.3075 Mex Recurrence Formula
タグ : / 解いたユーザー数 67
作問者 : 👑
binap
/ テスター :
Iroha_3856
hamamu
遭難者
問題文
非負整数列 $A = (A_1, A_2, \cdots)$ があります。
$A_1$ から $A_N$ までは入力で与えられており、第 $N+1$ 項以降は直前の $N$ 項の ${\rm mex}$ の値です。つまり $i = N + 1, N + 2, \cdots$ について以下の式が成立します。
$$A_i = {\rm mex}(A_{i-N}, A_{i-N+1}, \cdots, A_{i - 1})$$$A_X$ を求めてください。
$\rm mex$ とは
${\rm mex}(B_1, B_2, \cdots, B_M)$ とは集合 $\{B_1, B_2, \cdots, B_M\}$ に含まれない最小の非負整数を表します。例えば ${\rm mex}(2, 1, 0, 4) = 3, {\rm mex}(2, 2, 3) = 0$ となります。
制約
$1\leq N \leq 2\times 10^5$
$1\leq X \leq 10^{18}$
$0\leq A_i \leq 10^9$ $(1\leq i \leq N)$
入力は全て整数。
入力
$N$ $X$ $A_1$ $A_2$ $\cdots$ $A_N$
出力
$A_X$ の値を $1$ 行で出力してください。
サンプル
サンプル1
入力
4 6 1 0 1 3
出力
4
$A_5 = {\rm mex}(A_1, A_2, A_3, A_4) = {\rm mex}(1, 0, 1, 3) = 2$
$A_6 = {\rm mex}(A_2, A_3, A_4, A_5) = {\rm mex}(0, 1, 3, 2) = 4$
以下同様にして $A_5$ 以降の各項が計算されます。したがって数列 $A$ は $A = (1, 0, 1, 3, 2, 4, \cdots)$ となります。
サンプル2
入力
5 2 3 1 4 1 5
出力
1
サンプル3
入力
8 51 7 5 2 6 0 3 3 7
出力
8
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。