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 の場合、セットのサブセットは 1 つだけです。空のセットで、合計すると 0 になります。したがって、 と から始めeven=1ますodd=0。帰納的なステップ: 最初の k 個の要素の分割数が と であるevenとしoddます。

k+1 番目の数が偶数の場合、最初の k のサブセットよりも合計が偶数である場合、k+1 番目の要素を追加する (または追加しない) ことができ、偶数サブセットの数が 2 倍になります。合計が奇数のサブセットにも同じことが当てはまります。

k+1 番目の数が奇数の場合、合計が偶数である最初の k 数のサブセットは、k+1 番目の数で新しい偶数サブセットを与えませんが、合計が偶数である最初の k 数のサブセットはis odd は、k+1 番目が追加された場合、合計が偶数の 1 を返します。したがって、新しいものは古いものとevenの合計です。同様に、 newも同じ合計なので、 newは newと等しくなります。evenoddoddoddeven

even + odd == 2^k何があっても、すべての k について注意してください。そして、奇数になるとeven == odd、そのインデックスとそれ以上のすべてのインデックスに対して。

于 2013-07-03T17:16:38.107 に答える