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 から始まり、空集合を除く処理はどこにもありません。