No.3075 Mex Recurrence Formula
タグ : / 解いたユーザー数 70
作問者 : 👑
binap
/ テスター :
Iroha_3856
👑 
hamamu
👑 Problem Statement
There is a sequence of non-negative integers $A = (A_1, A_2, \cdots)$.
The terms $A_1$ through $A_N$ are given as input, and each term from the $N+1$-th onward is the ${\rm mex}$ of the immediately preceding $N$ terms. That is, the following formula holds for $i = N + 1, N + 2, \cdots$.
$$A_i = {\rm mex}(A_{i-N}, A_{i-N+1}, \cdots, A_{i - 1})$$Find $A_X$.
What is $\rm mex$?
${\rm mex}(B_1, B_2, \cdots, B_M)$ denotes the smallest non-negative integer not contained in the set $\{B_1, B_2, \cdots, B_M\}$. For example, ${\rm mex}(2, 1, 0, 4) = 3, {\rm mex}(2, 2, 3) = 0$.
Constraints
$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)$
All inputs are integers.
Input
$N$ $X$ $A_1$ $A_2$ $\cdots$ $A_N$
Output
Print the value of $A_X$ on $1$ line.
Sample
Sample 1
Input
4 6 1 0 1 3
Output
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$
The terms from $A_5$ onward are computed in the same way. Therefore, the sequence $A$ is $A = (1, 0, 1, 3, 2, 4, \cdots)$.
Sample 2
Input
5 2 3 1 4 1 5
Output
1
Sample 3
Input
8 51 7 5 2 6 0 3 3 7
Output
8
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。