2026-10-11
orders.rs
fn main() {
let n = 3;
let mut ways = vec![0u32; 1 << n];
ways[0] = 1;
for mask in 0..1usize << n {
for v in 0..n {
if mask & (1 << v) == 0 {
ways[mask | 1 << v] += ways[mask];
}
}
}
println!("{} {}", ways[0b110], ways[0b111]);
}
これは何を出力するでしょうか?
Answer
2 6 です。
ways[mask] は、mask のビットが立っている要素を1つずつ選んでいく順番が何通りあるかを数えます。外側のループで mask を取り、まだ選んでいない v ごとに ways[mask | 1 << v] へ ways[mask] を足します。mask | 1 << v は必ず mask より大きいので、mask を小さい順に回せば、どの集合も、そこから先へ足し込む前に自分への足し込みを受け終わっています。
0b110 は要素1と要素2の集合です。ways[0b010] と ways[0b100] は空集合から 1 ずつ受け取り、0b110 にはその両方から 1 ずつ届くので 2 になります。集合 {1, 2} は1つでも、そこへ至る順番は「1のあと2」と「2のあと1」の2通りあるからです。0b111 には 0b011、0b101、0b110 から 2 ずつ届いて 6 になり、3要素の並べ方 3! と一致します。