For problem statement at 0-999/400-499/450-459/453/problemD.txt this is a correct solution, but verifier at 0-999/400-499/450-459/453/verifierD.go ends with test 2 failed
input:
1 5 44
8 9
1 5
expected:
16
40
got:
36
24
exit status 1 can you fix the verifier? ```go
package main
import (
"bufio"
"io"
"math/bits"
"os"
"strconv"
)
var buf []byte
var pos int
func nextUint64() uint64 {
for pos < len(buf) && buf[pos] <= ' ' {
pos++
}
if pos >= len(buf) {
return 0
}
var res uint64
for pos < len(buf) && buf[pos] > ' ' {
res = res*10 + uint64(buf[pos]-'0')
pos++
}
return res
}
func mulMod(a, b, m uint64) uint64 {
hi, lo := bits.Mul64(a, b)
_, rem := bits.Div64(hi, lo, m)
return rem
}
func power(base, exp, M uint64) uint64 {
res := uint64(1)
base %= M
for exp > 0 {
if exp%2 == 1 {
res = mulMod(res, base, M)
}
base = mulMod(base, base, M)
exp /= 2
}
return res
}
func FWHT(a []uint64, M uint64) {
n := len(a)
for length := 1; length < n; length *= 2 {
for i := 0; i < n; i += 2 * length {
for j := 0; j < length; j++ {
u := a[i+j]
v := a[i+length+j]
sum := u + v
if sum >= M {
sum -= M
}
a[i+j] = sum
diff := u
if diff < v {
diff += M
}
diff -= v
a[i+length+j] = diff
}
}
}
}
func main() {
buf, _ = io.ReadAll(os.Stdin)
m := nextUint64()
t := nextUint64()
p := nextUint64()
N := uint64(1) << m
M := p * N
E := make([]uint64, N)
for i := uint64(0); i < N; i++ {
E[i] = nextUint64() % M
}
b := make([]uint64, m+1)
for i := uint64(0); i <= m; i++ {
b[i] = nextUint64() % M
}
B_full := make([]uint64, N)
for i := uint64(0); i < N; i++ {
pop := uint64(bits.OnesCount64(i))
B_full[i] = b[pop]
}
FWHT(B_full, M)
pow_W := make([]uint64, m+1)
for k := uint64(0); k <= m; k++ {
idx := (uint64(1) << k) - 1
pow_W[k] = power(B_full[idx], t, M)
}
FWHT(E, M)
for i := uint64(0); i < N; i++ {
pop := uint64(bits.OnesCount64(i))
E[i] = mulMod(E[i], pow_W[pop], M)
}
FWHT(E, M)
out := bufio.NewWriterSize(os.Stdout, 1<<20)
bufOut := make([]byte, 0, 20)
for i := uint64(0); i < N; i++ {
ans := E[i] / N
bufOut = strconv.AppendUint(bufOut[:0], ans, 10)
bufOut = append(bufOut, '\n')
out.Write(bufOut)
}
out.Flush()
}
```