問題一覧 > 通常問題

No.3075 Mex Recurrence Formula

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 67
作問者 : 👑 binap / テスター : Iroha_3856 hamamu 遭難者
8 ProblemId : 12092 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-03-24 23:58:58

問題文

非負整数列 A=(A1,A2,⋯ )A = (A_1, A_2, \cdots) があります。

A1A_1 から ANA_N までは入力で与えられており、第 N+1N+1 項以降は直前の NN 項の mex{\rm mex} の値です。つまり i=N+1,N+2,⋯i = N + 1, N + 2, \cdots について以下の式が成立します。

Ai=mex(Ai−N,Ai−N+1,⋯ ,Ai−1)A_i = {\rm mex}(A_{i-N}, A_{i-N+1}, \cdots, A_{i - 1})

AXA_X を求めてください。

mex\rm mex とは

mex(B1,B2,⋯ ,BM){\rm mex}(B_1, B_2, \cdots, B_M) とは集合 {B1,B2,⋯ ,BM}\{B_1, B_2, \cdots, B_M\} に含まれない最小の非負整数を表します。例えば mex(2,1,0,4)=3,mex(2,2,3)=0{\rm mex}(2, 1, 0, 4) = 3, {\rm mex}(2, 2, 3) = 0 となります。

制約

  • 1≤N≤2×1051\leq N \leq 2\times 10^5

  • 1≤X≤10181\leq X \leq 10^{18}

  • 0≤Ai≤1090\leq A_i \leq 10^9 (1≤i≤N)(1\leq i \leq N)

  • 入力は全て整数。

入力

NN XX
A1A_1 A2A_2 ⋯\cdots ANA_N

出力

AXA_X の値を 11 行で出力してください。

サンプル

サンプル1
入力
4 6
1 0 1 3
出力
4

  • A5=mex(A1,A2,A3,A4)=mex(1,0,1,3)=2A_5 = {\rm mex}(A_1, A_2, A_3, A_4) = {\rm mex}(1, 0, 1, 3) = 2

  • A6=mex(A2,A3,A4,A5)=mex(0,1,3,2)=4A_6 = {\rm mex}(A_2, A_3, A_4, A_5) = {\rm mex}(0, 1, 3, 2) = 4

以下同様にして A5A_5 以降の各項が計算されます。したがって数列 AA は A=(1,0,1,3,2,4,⋯ )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もしくは右上の雲マークをクリックしてアカウントを作成してください。