#848255 (Go) No.1142 XOR と XOR

• 問題: No.1142 XOR と XOR
• ユーザー: 草苺奶昔
• 提出日時: 2023-03-11 01:39:20
• 言語: Go (1.22.1)
• 結果: WA
• 実行時間: -
• コード長: 1,442 bytes
• コンパイル時間: 15,626 ms
• コンパイル使用メモリ: 222,632 KB
• 実行使用メモリ: 6,144 KB
• 最終ジャッジ日時: 2024-09-18 05:59:41
• 合計ジャッジ時間: 19,828 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	AC	124 ms; 5,376 KB
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	AC	150 ms; 6,016 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	1 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	WA	-
testcase_15	AC	75 ms; 5,376 KB
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	AC	120 ms; 5,376 KB
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-

ソースコード

package main

import (
	"bufio"
	"fmt"
	"os"
)

const MOD int = 1e9 + 7
const MAX int = 1024

func xorAndXor(nums1, nums2 []int, k int) int {
	f, g := make([]int, MAX), make([]int, MAX)
	f[0], g[0] = 1, 1
	xor := 0
	for _, num := range nums1 {
		xor ^= num
		f[xor]++
	}
	xor = 0
	for _, num := range nums2 {
		xor ^= num
		g[xor]++
	}

	f = XorConvolution(f, f)
	f[0] = ((f[0]-(len(nums1)+1))%MOD + MOD) % MOD
	g = XorConvolution(g, g)
	g[0] = ((g[0]-(len(nums2)+1))%MOD + MOD) % MOD

	res := XorConvolution(f, g)
	return res[k] / 4
}

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, m, k int
	fmt.Fscan(in, &n, &m, &k)
	nums1 := make([]int, n)
	nums2 := make([]int, m)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &nums1[i])
	}
	for i := 0; i < m; i++ {
		fmt.Fscan(in, &nums2[i])
	}

	fmt.Fprintln(out, xorAndXor(nums1, nums2, k))
}

func XorConvolution(a, b []int) []int {
	a = append(a[:0:0], a...)
	b = append(b[:0:0], b...)
	a = walshHadamardTransform(a, 1)
	b = walshHadamardTransform(b, 1)
	for i := range a {
		a[i] = a[i] * b[i] % MOD
	}
	res := walshHadamardTransform(a, (MOD+1)/2)
	return res
}

func walshHadamardTransform(f []int, op int) []int {
	n := len(f)
	for l, k := 2, 1; l <= n; l, k = l<<1, k<<1 {
		for i := 0; i < n; i += l {
			for j := 0; j < k; j++ {
				f[i+j], f[i+j+k] = (f[i+j]+f[i+j+k])*op%MOD, (f[i+j]+MOD-f[i+j+k])*op%MOD
			}
		}
	}
	return f
}