Submission #561965

#	Time	Username	Problem	Language	Result	Execution time	Memory
561965		jh05013	목공 (kriii4_A)	Pypy 3	100 / 100	2369 ms	30420 KiB

A

MOD = 1092616193
proot = 3
iproot = pow(proot, MOD-2, MOD)

def NTT(N, X, di):
    j = 0
    for i in range(1, N):
        k = N>>1
        while j >= k: j-= k; k>>= 1
        j+= k
        if i<j: X[i], X[j] = X[j], X[i]
    i = 1
    while i < N:
        x = pow(iproot if di else proot, MOD//i>>1, MOD); j = 0
        while j < N:
            y = 1
            for k in range(i):
                z = X[i|j|k]*y%MOD; X[i|j|k]= X[j|k]-z
                if X[i|j|k] < 0: X[i|j|k]+= MOD
                X[j|k]+= z
                if X[j|k] >= MOD: X[j|k]-= MOD
                y = y*x%MOD
            j+= i<<1
        i<<= 1
    if di:
        j = pow(N, MOD-2, MOD)
        for i in range(N): X[i] = X[i]*j%MOD

def poly_mul(P, Q):
    N = 1
    while len(P)+len(Q) > N: N<<= 1
    P = P[:]; Q = Q[:]
    for L in P, Q: L.extend([0]*(N-len(L)))
    NTT(N, P, 0); NTT(N, Q, 0)
    for i in range(N): P[i] = P[i]*Q[i] % MOD
    NTT(N, P, 1)
    while P and P[-1] == 0: P.pop()
    return P

# coeff of x^n in P/Q
def bm_onecoeff(P, Q, n):
    while n >= 1:
        Qm = [(x*(-1)**i)%MOD for i,x in enumerate(Q)]
        P = poly_mul(P, Qm)[n%2::2]
        Q = poly_mul(Q, Qm)[::2]
        n>>= 1
    return P[0] * pow(Q[0], MOD-2, MOD) % MOD

# n-th term of linear recurrence; next term is sum C[i]*ini[i]
def bostan_mori(C, ini, n):
    while C and C[-1] == 0: C.pop()
    if not C: return 0
    Q = [1%MOD]+[(-x)%MOD for x in reversed(C)]
    P = poly_mul(ini, Q)[:len(ini)]
    return bm_onecoeff(P, Q, n)

MIS = lambda: map(int,input().split())

n, m = MIS()
q = [int(input()) for i in range(n)]
idenom = pow(sum(q), MOD-2, MOD)
q = [x*idenom%MOD for x in q]

C = [-q[0]] + [q[i]-q[i+1] for i in range(len(q)-1)] + [q[-1]+1]
print(bostan_mori(C, [0]*n+[1], m))

• Subtask 1: 4 / 4
• Subtask 2: 96 / 96