題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟡 AT_dp_k Stones

Problem Statement

題目簡述

兩人進行取石子遊戲。初始有一堆 $K$ 個石子，給定一個集合 $A = \{ a_1, a_2, \ldots, a_N \}$ 。
兩人輪流操作，每次必須從 $A$ 中選擇一個數字 $x$ ，並從堆中取走 $x$ 個石子。
最終無法進行操作（即剩餘石子數小於 $A$ 中最小值）的一方判負。
假設雙方都採取最優策略，問先手是否獲勝。

Constraints

約束條件

$1 \leq N \leq 100$
$1 \leq K \leq 10^5$
$1 \leq a_1 < a_2 < \cdots < a_N \leq K$
輸入皆為整數

思路：博弈 DP

這是一個典型的 Impartial Game（公平組合遊戲）：雙方可選的操作完全相同、資訊完全透明（無隱藏資訊）、沒有隨機因素，且必定在有限步內結束。

為何狀態只有「必勝」與「必敗」兩種？

在上述條件下，雙方均可完美預測對手的最優行動。因此每個局面的結局是確定的：當前玩家或存在必勝策略，或無論如何操作都將落敗，二者必居其一。

狀態定義與轉移

設 $f[i]$ 表示剩餘 $i$ 個石子時，當前行動者是否必勝。

必敗態：所有後繼狀態皆為必勝態（無論怎麼走，對手都必勝）
必勝態：存在至少一個後繼狀態為必敗態（可以讓對手陷入必敗局面）

轉移方程：

f[i] = \bigvee_{x \in A,\, x \le i} \neg f[i-x]

初始條件： $f[0] = \text{False}$ （無法操作即判負）。

複雜度分析

時間複雜度： $\mathcal{O}(N \cdot K)$ 。狀態空間大小為 $K$ ，每個狀態轉移需要遍歷 $N$ 個選項。
空間複雜度： $\mathcal{O}(K)$ 。需要一個長度為 $K+1$ 的陣列來存儲狀態。

Code

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    assert len(A) == N

    f = [False] * (K + 1)
    for j in range(K + 1):
        for x in A:
            if j < x:
                break
            f[j] |= not f[j - x]
    print("First" if f[K] else "Second")

if __name__ == "__main__":
    solve()