Submission #1051733

---

Source Code Expand

omega = 103
n = 2**18
P = 5880*n + 1
rev = pow(omega, P-2, P)

def bit_reverse(d):
    n = len(d)
    ns = n>>1; nss = ns>>1
    ns1 = ns + 1
    i = 0
    for j in xrange(0, ns, 2):
        if j<i:
            d[i], d[j] = d[j], d[i]
            d[i+ns1], d[j+ns1] = d[j+ns1], d[i+ns1]
        d[i+1], d[j+ns] = d[j+ns], d[i+1]
        k = nss; i ^= k
        while k > i:
            k >>= 1; i ^= k
    return d

def fmt_bu(A, n, base, half, Q):
    N = n
    m = 1
    while n>1:
        n >>= 1
        w = pow(base, n, Q)
        wk = 1
        for j in xrange(m):
            for i in xrange(j, N, 2*m):
                U = A[i]; V = (A[i+m]*wk) % Q
                A[i] = (U + V) % Q
                A[i+m] = (U + V*half) % Q
            wk = (wk * w) % Q
        m <<= 1
    return A

def fmt(f, l, Q=P):
    if l == 1: return f
    A = f[:]
    bit_reverse(A)
    return fmt_bu(A, n, omega, pow(omega, n/2, Q), Q)

def ifmt(F, l, Q=P):
    if l == 1: return F
    A = F[:]
    bit_reverse(A)
    f = fmt_bu(A, n, rev, pow(rev, n/2, Q), Q)
    n_rev = pow(n, Q-2, Q)
    return [(e * n_rev) % Q for e in f]

def convolute(a, b, l, Q=P):
    A = fmt(a, l, Q)
    B = fmt(b, l, Q)
    C = [(s * t) % Q for s, t in zip(A, B)]
    c = ifmt(C, l, Q)
    return c

import sys
inp = map(int, sys.stdin.read().split())
m = inp[0]
f = inp[1::2] + [0]*(n-m)
g = inp[2::2] + [0]*(n-m)

fg = convolute(f, g, m)
sys.stdout.write("0\n")
sys.stdout.write("\n".join(map(str, fg[:2*m-1])))
sys.stdout.write("\n")

Submission Info

Judge Result