AtCoder Beginner Contest 390 D

https://atcoder.jp/contests/abc390/tasks/abc390_d

問題文の手順ではなく、Aの要素の袋への分配を全通り考えればよいです。それには、Aの要素を一つずつ足していけばよいです。入力例1なら、最初に[2]があって、そこに5を足すと[7], [2, 5]となります。

// Stone XOR
#![allow(non_snake_case)]

use std::collections::HashSet;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// process ////////////////////

fn read_input() -> Vec<u64> {
    let _N: usize = read();
    let A: Vec<u64> = read_vec();
    A
}

fn F(A: Vec<u64>) -> usize {
    let mut B: Vec<Vec<u64>> = vec![vec![A[0]]];
    for a in A[1..].into_iter() {
        let mut new_B: Vec<Vec<u64>> = vec![];
        for v0 in B.into_iter() {
            for i in 0..v0.len() {
                let mut v = v0.clone();
                v[i] += a;
                new_B.push(v)
            }
            let mut v = v0.clone();
            v.push(*a);
            new_B.push(v)
        }
        B = new_B
    }
    
    let mut s: HashSet<u64> = HashSet::new();
    for v in B.into_iter() {
        let n = v.into_iter().fold(0, |x, y| x ^ y);
        s.insert(n);
    }
    s.len()
}

fn main() {
    let A = read_input();
    println!("{}", F(A))
}