結果

問題 No.1142 XOR と XOR
コンテスト
ユーザー 草苺奶昔
提出日時 2023-03-11 01:39:20
言語 Go
(1.23.4)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

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
}
0