🤢

AtCoder Beginner Contest 390

2025/01/31に公開

難しい。

D問題

package main

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

func main() {

	var n int
	fmt.Scan(&n)

	reader := bufio.NewReaderSize(os.Stdin, 1<<20)

	line, _ := reader.ReadString('\n')
	line = strings.TrimSpace(line)
	parts := strings.Split(line, " ")
	a := make([]int, 0)

	for _, part := range parts {
		i, _ := strconv.Atoi(part)
		a = append(a, i)
	}

	ans := map[int]bool{}
	var b = []int{}
	var dfs func(int, int)

	dfs = func(i, xor int) {
		if i == n {
			ans[xor] = true
			return
		}

		v := a[i]
		b = append(b, v)

		dfs(i+1, xor^v)

		b = b[:len(b)-1]

		for j := range b {
			b[j] += v

			dfs(i+1, xor^(b[j]-v)^b[j])
			b[j] -= v
		}
	}

	dfs(0, 0)

	fmt.Println(len(ans))

}

Discussion