AtCoder Beginner Contest 386 E

https://atcoder.jp/contests/abc386/tasks/abc386_e

KがN/2以下のときはふつうに分割統治法を使えばよいですが、Kが大きいときは分割したときの個数が大きくなることがあります。例えば、N=100でK=99だと、100を2つで割って50個の有り無しになるので、2[sup]50[/sup]個の場合があって間に合いません。こういう場合は、K=1と考えるとよいです。全てのAのXORを取って、K=1のときの数とXORを取ればよいです。

// Diagonal Separation
#![allow(non_snake_case)]

use std::cmp::{min, max};


//////////////////// 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() -> (usize, Vec<u64>) {
    let v: Vec<usize> = read_vec();
    let K = v[1];
    let A: Vec<u64> = read_vec();
    (K, A)
}

fn DC(A: &[u64], K: usize) -> Vec<Vec<u64>> {
    if A.len() == 1 {
        return vec![vec![0], vec![A[0]]]
    }
    
    let mid = A.len() / 2;
    let v1 = DC(&A[..mid], K);
    let v2 = DC(&A[mid..], K);
    let L = min(A.len()+1, K+1);
    let mut v: Vec<Vec<u64>> = vec![vec![]; L];
    for (i, &ref w1) in v1.iter().enumerate() {
        if i > K {
            continue
        }
        for (j, &ref w2) in v2.iter().enumerate() {
            let k = i + j;
            if k > K {
                continue
            }
            for &n1 in w1.iter() {
                for &n2 in w2.iter() {
                    v[k].push(n1 ^ n2)
                }
            }
        }
    }
    v
}

fn F_core(K: usize, A: Vec<u64>, base: u64) -> u64 {
    let N = A.len();
    if N == 0 {
        return base
    }
    else if N == 1 {
        return A[0]
    }
    
    let mid = N / 2;
    let v1 = DC(&A[..mid], K);
    let v2 = DC(&A[mid..], K);
    let mut max_n: u64 = 0;
    for (i, &ref w1) in v1.iter().enumerate() {
        if i + v2.len() < K || i > K {
            continue
        }
        let j = K - i;
        for &n1 in w1.iter() {
            for &n2 in v2[j].iter() {
                let n = n1 ^ n2 ^ base;
                max_n = max(n, max_n)
            }
        }
    }
    max_n
}

fn F(K: usize, A: Vec<u64>) -> u64 {
    if K > A.len() / 2 {
        let total = A.iter().fold(0, |x, &y| x ^ y);
        F_core(A.len() - K, A, total)
    }
    else {
        F_core(K, A, 0)
    }
}

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