2

我在一个让我困惑的 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。是对的吗？如果是这样，为什么要跟踪偶数/奇数计数？

4

1 回答 1

4

这根本不需要迭代程序。假设您的集合有 N 个元素，k 个偶数和 Nk 个奇数。那么，这 k 个偶数并不真正相关；它们的 2^k 个组合中的任何一个，以及具有偶数和的奇数子集，组合成一个偶数和。

奇数的组合有多少个和是偶数？如果 Nk > 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个数的和为偶数的子集如果附加了第 k+1 个，则为奇数给出一个偶数和。所以，新even是旧even和的总和odd。同样， newodd也是相同的总和，所以 newodd等于 new even。

请注意，even + odd == 2^k对于所有 k，无论如何。并且，一旦有一个奇数，even == odd该指数和所有更高的指数。

于 2013-07-03T17:16:38.107 回答