POJ 3370 Halloween Treats：抽屜原理 + 前綴和模運算求子集

題目重述

c 個孩子，n 個鄰居（c ≤ n ≤ 10⁵），第 i 個鄰居給 aᵢ 顆糖。選一個非空子集，使總糖數能被 c 整除（每個孩子至少分到 1 顆，即總和 ≥ c）。輸出任一合法子集的鄰居編號（1-based），無解印 no sweets。

核心定理：鴿巢原理保證解的存在性

考慮前綴和 Sₖ = (a₁ + ... + aₖ) mod c（k = 1..n）。共有 n 個值，取值範圍 [0, c-1]（共 c 種）。因 n ≥ c，由鴿巢原理：

• 若某 Sₖ = 0，則 [1, k] 即為解；
• 否則必有 i < j 使 Sᵢ = Sⱼ，則 [i+1, j] 區間和模 c 為 0。

因此一定存在連續子區間解，且長度 ≤ c。題目允許輸出任意解，故只需找連續區間即可。

O(n) 線性掃描算法

mod[0] = 0; // 虛擬前綴和索引 0
for i = 1..n:
    read a[i]
    sum = (sum + a[i]) % c
    if (mod[sum] != -1): // 找到相同餘數
        L = mod[sum] + 1
        R = i
        output L..R
        break
    else:
        mod[sum] = i
// 若循環結束未 break，理論上不可能（因 n≥c），但為保險輸出 no sweets

• mod[r] 記錄「首次出現餘數 r 的前綴索引」，初始 -1，mod[0]=0。
• 找到即輸出並處理下一測資；c, n ≤ 10⁵，aᵢ ≤ 10⁵，int 足夠（累加用 long long 取模）。

邊界情況：每個孩子至少 1 顆糖

找到的區間和為 c 的倍數。若倍數為 0（即區間和 = 0），因 aᵢ ≥ 1，只有空區間和為 0，但演算法找到的區間長度 ≥ 1，故和 ≥ c ≥ 1，自動滿足「至少 1 顆」。

複雜度

• 時間 O(n)，空間 O(c)，極優。
• 多測資，c=n=0 結束。

總結

本題是「抽屜原理在前綴和模運算中應用」的教科書範例。關鍵洞察：模 c 餘數只有 c 種，n ≥ c 保證重複，從而將任意子集問題降維為連續區間問題，實現 O(n) 線性解法。無需 DP、背包或搜尋，極其優雅。