🤢
AtCoder Beginner Contest 390
難しい。
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