Namaran

Code daily. Without assist.

2026-11-09

subset_count.cpp

#include <print>

int main() {
    int a[] = {3, 5, 8};
    int count = 0;
    for (int mask = 0; mask < (1 << 3); ++mask) {
        int sum = 0;
        for (int i = 0; i < 3; ++i) {
            if ((mask >> i) & 1) {
                sum += a[i];
            }
        }
        if (sum % 8 == 0) {
            ++count;
        }
    }
    std::println("{}", count);
}

これは何を出力するでしょうか?

Answer

Output

4

mask は0から (1 << 3) - 1(7)までの8通りを動き、mask の i ビット目が1なら a[i] を選んだとみなします。3要素の部分集合は23 = 8個あり、8つの mask がちょうど1つずつに対応します。mask の順に和を並べると、0(何も選ばない)、3、5、8(3と5)、8(8だけ)、11、13、16です。8で割り切れるのは0、8、8、16の4つなので、count は4になります。

見落としやすいのは mask が0のときです。0はどのビットも立っていないので、内側のループは何も足さず、sum は0のまま残ります。これは要素を1つも選ばない空の部分集合で、0 % 8 は0なので条件を満たします。部分集合と聞いて要素を選んだものだけを思い浮かべると、3と5の組と8だけの組と全部の組を数えて3と答えます。ループは mask = 0 から始まり、空集合を除く処理はどこにもありません。