概要

この問題は、各マスから次に行くマスが1つに決まる「関数グラフ」上で、始点から \(K\) 回遷移した先を求める問題です。
\(K\) が最大 \(10^{18}\) と非常に大きいため、1回ずつシミュレーションせず、ダブリング（binary lifting）で高速に求めます。

考察

まず、盤面のルールを見ると「現在位置 \(i\) が決まれば、次の位置も一意に決まる」ことが分かります。

• \(i=N\) なら常に \(N\)
• \(i=1\) なら \(A_1+A_2\) の偶奇で \(1\) or \(2\)
• \(2\le i\le N-1\) なら \(A_i+A_{i+1}\) の偶奇で \(i-1\) or \(i+1\)

つまり、各マスに対して「次のマス」nxt[i] を前計算できます。
ここまでできると問題は次の形になります：

• 長さ \(N\) の配列 nxt がある
• 初期位置は 0（1-indexed のマス1）
• pos = nxt[pos] を \(K\) 回繰り返した最終位置を求める

---

素朴解がなぜだめか

素朴に \(K\) 回ループすると \(O(K)\) です。
しかし \(K \le 10^{18}\) なので、これは到底間に合いません。

---

どう解決するか

\(K\) 回遷移を2進数分解して処理します（ダブリング）。

• up[b][i] := 「マス i から \(2^b\) 回移動した先」
• up[0][i] = nxt[i]
• up[b+1][i] = up[b][ up[b][i] ]

こうしておけば、\(K\) のビットを見て
- \(b\) ビット目が1なら pos = up[b][pos]
と進めるだけで、合計 \(O(\log K)\) 回で最終位置を求められます。

\(K \le 10^{18} < 2^{60}\) なので、60段あれば十分です。

アルゴリズム

1. 入力を受け取る。
2. 特殊ケース N=1 は常にマス1なので即出力。
3. 0-indexed で nxt を作る。
   • i=N-1 は自分自身
   • i=0 は (A[0]+A[1]) の偶奇で 0 or 1
   • それ以外は (A[i]+A[i+1]) の偶奇で i-1 or i+1
4. ダブリング表 up を構築する（60段）。
5. 初期位置 pos=0 から、\(K\) の各ビットを見てジャンプ。
6. 1-indexed に戻して pos+1 を出力。

計算量

• 時間計算量: \(O(N \log K)\)
• 空間計算量: \(O(N \log K)\)

実装のポイント

• 添字は実装上 0-indexed にすると楽です（最後に +1 して出力）。

• 偶奇判定は (x & 1) で高速に書けます。負数でも Python では問題ありません。

• LOG=60 は \(K\le 10^{18}\) に対して十分です。

• N=1 を先に処理しないと A[1] 参照で範囲外になるので注意。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    if N == 1:
        print(1)
        return

    # next position for each square (0-indexed)
    nxt = [0] * N
    for i in range(N):
        if i == N - 1:
            nxt[i] = i
        elif i == 0:
            nxt[i] = 1 if ((A[0] + A[1]) & 1) == 0 else 0
        else:
            nxt[i] = i + 1 if ((A[i] + A[i + 1]) & 1) == 0 else i - 1

    LOG = 60  # since K <= 1e18 < 2^60
    up = [nxt]
    for _ in range(1, LOG):
        prev = up[-1]
        cur = [0] * N
        for i in range(N):
            cur[i] = prev[prev[i]]
        up.append(cur)

    pos = 0  # start from square 1 (0-indexed)
    b = 0
    while K:
        if K & 1:
            pos = up[b][pos]
        K >>= 1
        b += 1

    print(pos + 1)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.3-codex によって生成されました。