D - Stone XOR
Source: atcoder
Difficulty: 400

Problem Statement
There are
N
bags, labeled bag
1
, bag
2
,
\ldots
, bag
N
.
Bag
i
(
1 \leq i \leq N
) contains
A_i
stones.
Takahashi can perform the following operation any number of times, possibly zero:
Choose two bags A and B, and move
all
stones from bag A into bag B.
Find the number of different possible values for the following after repeating the operation.
B_1 \oplus B_2 \oplus \cdots \oplus B_N
, where
B_i
is the final number of stones in bag
i
.
Here,
\oplus
denotes bitwise XOR.
About bitwise XOR
For non-negative integers
a
and
b
, the bitwise XOR
a \oplus b
is defined as follows:
In the binary representation of
a \oplus b
, the digit in the
2^k
place (
k \ge 0
) is
1
if and only if exactly one of the digits in the
2^k
place of
a
and
b
is
1
; otherwise, it is
0
.
For example,
3 \oplus 5 = 6
(in binary,
011 \oplus 101 = 110
).
In general, for
k
non-negative integers
x_1, x_2, \ldots, x_k
, their bitwise XOR
x_1 \oplus x_2 \oplus \cdots \oplus x_k
is defined as
(\cdots((x_1 \oplus x_2) \oplus x_3) \oplus \cdots) \oplus x_k
, which does not depend on the order of
x_1, x_2, \ldots, x_k
.
It can be proved that under the constraints of this problem, the number of possible values is finite.
Constraints
2 \leq N \leq 12
1 \leq A_i \leq 10^{17}
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_1
A_2
\ldots
A_N
Output
Print the number of different possible values for
B_1 \oplus B_2 \oplus \cdots \oplus B_N
after repeating the operation.
Sample Input 1
3
2 5 7
Sample Output 1
3
For example, if Takahashi chooses bags
1
and
3
for the operation, then the numbers of stones in bags
1, 2, 3
become
0, 5, 9
.
If he stops at this point, the XOR is
0 \oplus 5 \oplus 9 = 12
.
The other possible XOR values after repeating the operation are
0
and
14
.
Therefore, the possible values are
0, 12, 14
; there are three values, so the output is
3
.
Sample Input 2
2
100000000000000000 100000000000000000
Sample Output 2
2
Sample Input 3
6
71 74 45 34 31 60
Sample Output 3
84

C++ solution:
#ifdef LOCAL
//#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < (ll)n; i++)
#define all(v) v.begin(),v.end()
const ll INF = (ll)2e18;
vector<ll> seen;
ll N;
vector<ll> A;

void f(ll pos,vector<ll>&v){
    if(pos==N){
        ll ret = 0;
        rep(i,v.size()){
            ret ^= v[i];
        }
        seen.push_back(ret);
        return;
    }
    rep(i,v.size()){
        v[i] += A[pos];
        f(pos + 1, v);
        v[i] -= A[pos];
    }
    v.push_back(A[pos]);
    f(pos + 1, v);
    v.pop_back();
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N;
    A.resize(N);
    rep(i, N) cin >> A[i];
    vector<ll>v;

    f(0, v);
    sort(all(seen));
    seen.erase(unique(all(seen)), seen.end());

    cout << seen.size() << endl;
}
/*
12の分割数は77
愚直なら12^12
後ろに付け加える感じにすれば少なくなる
    N!=4.8*10^9
    運が良ければ通るかもくらい...
        厳密に計算すると、もっと少ないじゃん

順番にも意識する？

12個の石を0以上の要素数の12個の集合に分ける方法
    (12+11)!/12!11!
    =1352078



*/

Go solution:
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

// 9223372036854775808, 19 digits, 2^63
const INT_MAX = math.MaxInt

// -9223372036854775808, 19 digits, -1 * 2^63
const INT_MIN = math.MinInt

var r = bufio.NewReader(os.Stdin)
var w = bufio.NewWriter(os.Stdout)

func main() {
	defer w.Flush()

	N := readInt(r)
	As := readIntArr(r)

	ansMap := make(map[int]struct{})

	groups := make([]int, 0, N)
	var dfs func(idx int)
	dfs = func(idx int) {
		if idx == N {
			xor := 0
			for _, g := range groups {
				xor ^= g
			}
			ansMap[xor] = struct{}{}
			return
		}

		for gi := range groups {
			groups[gi] += As[idx]
			dfs(idx + 1)
			groups[gi] -= As[idx]
		}

		groups = append(groups, As[idx])
		dfs(idx + 1)
		groups = groups[:len(groups)-1]
	}

	dfs(0)

	fmt.Println(len(ansMap))
}

//////////////
// Libs    //
/////////////

//////////////
// Helpers //
/////////////

// 一行に1文字のみの入力を読み込む
func readStr(r *bufio.Reader) string {
	input, _ := r.ReadString('\n')
	return strings.TrimSpace(input)
}

// 一行に1つの整数のみの入力を読み込む
func readInt(r *bufio.Reader) int {
	input, _ := r.ReadString('\n')
	str := strings.TrimSpace(input)
	i, _ := strconv.Atoi(str)
	return i
}

// 一行に2つの整数のみの入力を読み込む
func read2Ints(r *bufio.Reader) (int, int) {
	input, _ := r.ReadString('\n')
	strs := strings.Fields(input)
	i1, _ := strconv.Atoi(strs[0])
	i2, _ := strconv.Atoi(strs[1])
	return i1, i2
}

// 一行に複数の文字列が入力される場合、スペース区切りで文字列を読み込む
func readStrArr(r *bufio.Reader) []string {
	input, _ := r.ReadString('\n')
	return strings.Fields(input)
}

// 一行に複数の整数が入力される場合、スペース区切りで整数を読み込む
func readIntArr(r *bufio.Reader) []int {
	input, _ := r.ReadString('\n')
	strs := strings.Fields(input)
	arr := make([]int, len(strs))
	for i, s := range strs {
		arr[i], _ = strconv.Atoi(s)
	}
	return arr
}

// height行の文字列グリッドを読み込む
func readGrid(r *bufio.Reader, height int) [][]string {
	grid := make([][]string, height)
	for i := 0; i < height; i++ {
		str := readStr(r)
		grid[i] = strings.Split(str, "")
	}
	return grid
}

// height行の整数グリッドを読み込む
func readIntGrid(r *bufio.Reader, height int) [][]int {
	grid := make([][]int, height)
	for i := 0; i < height; i++ {
		grid[i] = readIntArr(r)
	}

	return grid
}

// height行、width列のT型グリッドを作成
func createGrid[T any](height, width int, val T) [][]T {
	grid := make([][]T, height)
	for i := 0; i < height; i++ {
		grid[i] = make([]T, width)
		for j := 0; j < width; j++ {
			grid[i][j] = val
		}
	}
	return grid
}

// 文字列グリッドを出力する
func writeGrid(w *bufio.Writer, grid [][]string) {
	for i := 0; i < len(grid); i++ {
		fmt.Fprint(w, strings.Join(grid[i], ""), "\n")
	}
}

// スライスの中身をスペース区切りで出力する
func writeSlice[T any](w *bufio.Writer, sl []T) {
	vs := make([]any, len(sl))
	for i, v := range sl {
		vs[i] = v
	}
	fmt.Fprintln(w, vs...)
}

// スライスの中身をスペース区切りなしで出力する
func writeSliceWithoutSpace[T any](w *bufio.Writer, sl []T) {
	if len(sl) == 0 {
		fmt.Fprintln(w)
		return
	}

	for idx, v := range sl {
		fmt.Fprint(w, v)
		if idx == len(sl)-1 {
			fmt.Fprintln(w)
		}
	}
}

// スライスの中身を一行づつ出力する
func writeSliceByLine[T any](w *bufio.Writer, sl []T) {
	if len(sl) == 0 {
		fmt.Fprintln(w)
		return
	}

	for _, v := range sl {
		fmt.Fprintln(w, v)
	}
}

func atoi(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}

func itoa(n int) string {
	return strconv.Itoa(n)
}

func sort2Ints(a, b int) (int, int) {
	if a > b {
		return b, a
	}
	return a, b
}

func sort2IntsDesc(a, b int) (int, int) {
	if a < b {
		return b, a
	}
	return a, b
}

func mapKeys[T comparable, U any](m map[T]U) []T {
	keys := make([]T, 0, len(m))
	for k := range m {
		keys = append(keys, k)
	}
	return keys
}

func min(i, j int) int {
	if i < j {
		return i
	}
	return j
}

func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

// O(log(exp))
// 繰り返し二乗法で x^y を計算する関数
func pow(base, exp int) int {
	if exp == 0 {
		return 1
	}

	// 繰り返し二乗法
	// 2^8 = 4^2^2
	// 2^9 = 4^2^2 * 2
	// この性質を利用して、基数を2乗しつつ指数を1/2にしていく
	result := 1
	for exp > 0 {
		if exp%2 == 1 {
			result *= base
		}
		base *= base
		exp /= 2
	}
	return result
}

//////////////
// Debug   //
/////////////

var dumpFlag bool

func init() {
	args := os.Args
	dumpFlag = len(args) > 1 && args[1] == "-dump"
}

func dump(format string, a ...interface{}) {
	if dumpFlag {
		fmt.Printf(format, a...)
	}
}

Java solution:
import java.util.HashSet;
import java.util.Scanner;

public class Main {

    static long[] a = new long[12];
    static long[] b = new long[12];
    static int k = 0;

    static HashSet<Long> set;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }
        set = new HashSet<>(10000000);
        dfs(n-1);
        System.out.println(set.size());
    }

    static long val = 0;
    static void dfs(int l) {
        if (l==-1){
            // 异或运算的单位元是0
            set.add(val);
        } else {
            for (int i = 0; i < k; i++) {
                val ^= b[i];
                b[i] = b[i] + a[l];
                val ^= b[i];
                dfs(l-1);
                // 回溯是返回上一个状态
                val ^= b[i];
                b[i] = b[i] - a[l];
                val ^= b[i];
            }
            b[k] += a[l];
            val ^= b[k];
            k++;
            dfs(l-1);
            k--;
            val ^= b[k];
            b[k] = 0;
        }
    }

}

JavaScript solution:
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let n = 0;
let a = [];
let possibleXorSums = new Set();

function dfs(index, groupSums, currentXor) {
    if (index === n) {
        possibleXorSums.add(currentXor);
        return;
    }

    // Option 1: Add the current stone to an existing group
    for (let i = 0; i < groupSums.length; i++) {
        const oldSum = groupSums[i];
        const newSum = oldSum + a[index];
        groupSums[i] = newSum;
        const nextXor = currentXor ^ oldSum ^ newSum;
        dfs(index + 1, groupSums, nextXor);
        groupSums[i] = oldSum; // Backtrack
    }

    // Option 2: Create a new group with the current stone
    groupSums.push(a[index]);
    const nextXor = currentXor ^ a[index];
    dfs(index + 1, groupSums, nextXor);
    groupSums.pop(); // Backtrack
}

function solve() {
    let inputLines = [];
    rl.on('line', (line) => {
        inputLines.push(line.trim());
        if (inputLines.length === 2) {
            n = parseInt(inputLines[0], 10);
            a = inputLines[1].split(' ').map(BigInt);
            dfs(0, [], 0n);
            console.log(possibleXorSums.size);
            rl.close();
        }
    });
}

solve();

Python solution:
import sys

n = 0
a = []
possible_xor_sums = set()

def dfs(index, groups_sums, current_xor):
    if index == n:
        possible_xor_sums.add(current_xor)
        return

    for i in range(len(groups_sums)):
        old_sum = groups_sums[i]
        new_sum = old_sum + a[index]
        groups_sums[i] = new_sum

        next_xor = current_xor ^ old_sum ^ new_sum

        dfs(index + 1, groups_sums, next_xor)

        groups_sums[i] = old_sum

    groups_sums.append(a[index])

    next_xor = current_xor ^ a[index]

    dfs(index + 1, groups_sums, next_xor)

    groups_sums.pop()


def solve():
    global n, a
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))

    dfs(0, [], 0)

    print(len(possible_xor_sums))

solve()

Ruby solution:
N = gets.split.map( &:to_i )[0]
A = gets.split.map( &:to_i )

@g   = Array.new(N){ 0 }
@xor = 0
@sum = []
@count = 0

def grouping idx, g_sz
  if idx == N
    @sum << @xor
#    p [g_sz, @g]
  else
    (g_sz + 1).times {|i|
#      p [@g,i, A,idx]
      @xor ^= @g[i]
      @g[i] += A[idx]
      @xor ^= @g[i]
      if i == g_sz
        grouping( idx + 1, g_sz + 1 )
      else
        grouping( idx + 1, g_sz )
      end
      @xor ^= @g[i]
      @g[i] -= A[idx]
      @xor ^= @g[i]
    }
  end
end



grouping 0, 0

p @sum.uniq.size