Namaran

Code daily. Without assist.

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つを落とします。