這段代碼如何計算一組正整數的所有子集的總和是偶數？

Question

我在一個令我困惑的TopCoder解決方案中遇到了這段代碼。有一個正整數和正整數的數組列表。我認爲它返回的總和是模數MOD的子集數。我相信MOD只是爲了避免溢出，如果列表很大，所以如果你保持數字少於32，那麼我認爲你不需要它。

ArrayList l = { ... positive even and odd integers ... }; 

int dp[] = {1,0}; 
for (int i = 0; i < l.size(); ++i) { 
     int even = dp[0]; 
     int odd = dp[1]; 
     if (l.get(i) % 2 == 0) { 
       even *= 2; 
       odd *= 2; 
     } else { 
       even += odd; 
       odd = even; 
     } 
     dp[0] = even % MOD; 
     dp[1] = odd % MOD; 
} 
return (dp[0] - 1 + MOD) % MOD; 

如果所有整數都是偶數，那麼我認爲答案是2^N-1。 但似乎如果有至少一個奇數整數，答案變成2 ^（N-1）-1。是對的嗎？如果是這樣，爲什麼跟蹤偶數/奇數？

Answer 1

這根本不需要迭代程序。假設你的集合有N個元素，k個偶數和N-k個奇數。那麼，k個偶數並不是真正相關的;它們中的任何2^k個組合，連同具有偶數的奇數的子集一起，組合成偶數和。

奇數有多少組合有偶數？如果N-k> 0，則有2 ^（N - k - 1）個。所以，你是對的。這是一個編碼問題，而不是數學問題。

但給定的算法如下：

當N = 0，僅存在一個所述組的子集：空集，這總計爲0，所以，開始與even=1和odd=0。現在是歸納步驟：假設前k個元素的分區數是even和odd。

如果第k + 1個數是偶數，那麼它的總和爲偶數的第一個k的任何子集可以附加（或不附加）第k + 1個元素，使偶數子集數加倍。這同樣適用於具有奇數和的子集。

如果第k + 1個數是奇數，那麼其總和爲偶數的前k個數的任何子集都不會給出具有第k + 1個數的任何新的偶數子集，而第一個子集如果第k + 1個附加，則其總和爲奇數的k個數字給出一個具有偶數和的數字。所以，新的even是舊的even和odd的總和。同樣，新的odd也是相同的總和，所以新的odd等於新的even。

請注意，所有k的even + odd == 2^k，無論如何。而且，一旦出現奇數，該指數的所有指標均爲even == odd。