先計算砝碼總重量 wsum，如果 wsum 是奇數，不可能平分，直接輸出 0。接下來要湊出 target = wsum/2，每個砝碼只有選或不選兩種可能性，是 0/1 背包問題，可以用 dp[i] 代表總重量為 i 時的方法數，也可以用 bitset 代表是否能湊出總重量 i。這題如果用 bitset 解題， Python 可以 7 ms AC，C++ 可以 1 ms AC。

先計算砝碼總重量 wsum，如果 wsum 是奇數，不可能平分，直接輸出 0。接下來要湊出 target = wsum/2，每個砝碼只有選或不選兩種可能性，是 0/1 背包問題，可以用 dp[i] 代表總重量為 i 時的方法數，也可以用 bitset 代表是否能湊出總重量 i。這題如果用 bitset 解題， Python 可以 7 ms AC，C++ 可以 1 ms AC。

還有一點，如果用 C++ 解題並計算方法數，要用 unsigned long long 儲存方法數才行，否則會溢位，有兩筆測資不過。不然就是在計算方法數的過程中對一個有點大的質數取 mod，讓方法數不會超出 int 的範圍。

先計算砝碼總重量 wsum，如果 wsum 是奇數，不可能平分，直接輸出 0。接下來要湊出 target = wsum/2，每個砝碼只有選或不選兩種可能性，是 0/1 背包問題，可以用 dp[i] 代表總重量為 i 時的方法數，也可以用 bitset 代表是否能湊出總重量 i。這題如果用 bitset 解題， Python 可以 7 ms AC，C++ 可以 1 ms AC。

還有一點，如果用 C++ 解題並計算方法數，要用 unsigned long long 儲存方法數才行，否則會溢位，有兩筆測資不過。不然就是在計算方法數的過程中對一個有點大的質數取 mod，讓方法數不會超出 int 的範圍。

您好，

　　感謝您提供的題解！

　　關於後半段提到需要使用 unsigned long long 或取模來避免溢位，這部分其實是因為 DP 狀態設計為「方法數」所致。由於本題只需判斷是否存在可行解，實際上只需要用 bool（或 bitset）來表示「方法數是否大於 0」，即可避免溢位問題，這部分也有看到您的提交結果。

　　後續我會視情況考慮是否要生測資把 unsigned long long 的解卡掉，如果時間允許的話 😅，不過質數我就無能為力了，這本質上是一個只有 $\frac{1}{p}$ 機率會錯的解，即便卡掉一個常見的質數，再隨便換一個就過了。

M_SQRT