2026-08-26
count_subsets.rs
fn main() {
let a = [1, 2, 3];
let mut count = 0;
for mask in 0..1 << a.len() {
let mut sum = 0;
for (i, x) in a.iter().enumerate() {
if mask >> i & 1 == 1 {
sum += x;
}
}
if sum % 3 == 0 {
count += 1;
}
}
println!("{count}");
}
これは何を出力するでしょうか?
Answer
Output
4
mask は 0..1 << a.len() の範囲で、0から7までの8通りの値を取ります。mask >> i & 1 == 1 は mask の i ビット目が1かを調べる式で、1なら a[i] を和に入れます。Rust では >> が & より、& が == より先に結び付くので、この式は ((mask >> i) & 1) == 1 と読みます。3要素からいくつかを選ぶ選び方は2の3乗の8通りで、mask の8つの値と1つずつ対応します。
8通りの和は、mask の順に 0、1、2、3、3、4、5、6 です。3で割り切れるのは、mask が0の和0、3の {1, 2} の和3、4の {3} の和3、7の {1, 2, 3} の和6の4つです。
mask が0のときは、どのビットも0なので何も選ばず、和は0のままです。0は3で割り切れるので、この何も選ばない選び方も数えられます。和が3と6になる選び方だけを数えて 3 と答えると、この1つを落とします。