Problem:


Score : 600 points

Problem Statement

Given are a prime number p and a sequence of p integers a_0, \ldots, a_{p-1} consisting of zeros and ones.

Find a polynomial of degree at most p-1, f(x) = b_{p-1} x^{p-1} + b_{p-2} x^{p-2} + \ldots + b_0, satisfying the following conditions:

For each i (0 \leq i \leq p-1), b_i is an integer such that 0 \leq b_i \leq p-1.

For each i (0 \leq i \leq p-1), f(i) \equiv a_i \pmod p.

Constraints

2 \leq p \leq 2999

p is a prime number.

0 \leq a_i \leq 1

Input

Input is given from Standard Input in the following format:

p
a_0 a_1 \ldots a_{p-1}

Output

Print b_0, b_1, \ldots, b_{p-1} of a polynomial f(x) satisfying the conditions, in this order, with spaces in between.

It can be proved that a solution always exists. If multiple solutions exist, any of them will be accepted.

Sample Input 1

2
1 0

Sample Output 1

1 1

f(x) = x + 1 satisfies the conditions, as follows:

f(0) = 0 + 1 = 1 \equiv 1 \pmod 2

f(1) = 1 + 1 = 2 \equiv 0 \pmod 2

Sample Input 2

3
0 0 0

Sample Output 2

0 0 0

f(x) = 0 is also valid.

Sample Input 3

5
0 1 0 1 0

Sample Output 3

0 2 0 1 3



Sample input:
2
1 0


Sample output:
1 1

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
p=int(input())
A=[int(i) for i in input().split()]
B=[0]*p

P=[[0]*p for _ in range(p)]
for i in range(1,p): 
  for j in range(1,p):
    if j==1:
      P[i][j]=i
    else:
      P[i][j]=(P[i][j-1]*i)%p

for i in range(p):
  a=A[i]
  B[0]-=a
  for j in range(1,p):
    B[j]-=a*P[i][j]
    if j==p-1:
      B[j]+=a
B=B[::-1]
for i in range(p):
  B[i]%=p
print(*B)

Submission status: Time Limit Exceeded

Solution code:
p = int(input())
A = [int(x) for x in input().split()]

def swap(a, b):
        return (b, a)

def modinv(a, m):
        b = m
        u = 1
        v = 0
        while b:
                t = a // b
                a -= t * b
                a, b = swap(a, b)
                u -= t * v
                u, v = swap(u, v)
        u %= m
        if u < 0:
                u += m
        return u

# p-1C0, p-1C1, ..., p-1Cp-1
binomial = []
for i in range(p):
    num = 1
    denom = 1
    for j in range(1, i+1):
        num *= (p-j)
        denom *= j
        num %= p
        denom %= p
    binomial.append(num * modinv(denom, p) % p)

ret = [0] * p
for i in range(p):
    if A[i] == 0:
        continue

    ret[0] += 1
    for j in range(p):
        ret[j] -= binomial[j] * (-i) ** (p-1-j)
        ret[j] %= p

ans = ''
for i in range(p):
    ans += str(ret[i]%p) + ' '

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
p=int(input())
A=[int(i) for i in input().split()]
mod=p
B=[0]*p
for i in range(p):
  c=1
  B[0]-=A[i]
  for j in range(1,p):
    c*=i
    B[j]-=A[i]*c
    if j==p-1:
      B[j]+=A[i]
B=B[::-1]
for i in range(p):
  B[i]=B[i]%mod
print(*B)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
p=int(input())
A=[int(i) for i in input().split()]
mod=p
B=[0]*p
for i in range(p):
  C=[1]*p
  B[0]=(B[0]-A[i])%mod
  for j in range(1,p):
    C[j]=(C[j-1]*i)%mod
    B[j]=(B[j]-A[i]*C[j])%mod
    if j==p-1:
      B[j]=(B[j]+A[i])%mod
B=B[::-1]
print(*B)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import functools
INF = float("inf")

MOD = 2  # type: int


def power(b, p):
    if p == 0:
        return 1
    elif p == 1:
        return b
    elif p % 2 == 1:
        return b*power(b, p-1)
    else:
        return power(b*b, p//2)


def solve(p: int, a: "List[int]"):
    kaijo = [1]*p
    kaijo_inv = [1]*p

    for i in range(2, p):
        kaijo[i] = (kaijo[i-1]*i) % p
        kaijo_inv[i] = power(kaijo[i], p-2) % p

    @functools.lru_cache(maxsize=None)
    def cmb(n, r):
        return (kaijo[n]*kaijo_inv[n-r]*kaijo_inv[r]) % p

    b = [0]*p
    for ai, av in enumerate(a):
        if av == 1:
            for i in range(p):
                b[i] += -cmb(p-1, i) * power(-ai, p-i-1)
                b[i] %= p
            b[0] += 1
            b[0] %= p
    print(*b, sep=" ")
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    p = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(p-1-0+1)]  # type: "List[int]"
    solve(p, a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import functools
INF = float("inf")

MOD = 2  # type: int


def power(b, p):
    if p == 0:
        return 1
    elif p == 1:
        return b
    elif p % 2 == 1:
        return b*power(b, p-1)
    else:
        return power(b*b, p//2)


def solve(p: int, a: "List[int]"):
    kaijo = [1]*p
    kaijo_inv = [1]*p

    for i in range(2, p):
        kaijo[i] = (kaijo[i-1]*i) % p
        kaijo_inv[i] = power(kaijo[i], p-2) % p

    def cmb(n, r):
        return (kaijo[n]*kaijo_inv[n-r]*kaijo_inv[r]) % p

    b = [0]*p
    for ai, av in enumerate(a):
        if av == 1:
            for i in range(p):
                b[i] += -cmb(p-1, i) * power(-ai, p-i-1)
                b[i] %= p
            b[0] += 1
            b[0] %= p
    print(*b, sep=" ")
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    p = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(p-1-0+1)]  # type: "List[int]"
    solve(p, a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import functools
INF = float("inf")

MOD = 2  # type: int


@functools.lru_cache(maxsize=None)
def cmb(n, r):
    r = min(r, n-r)
    if r == 0:
        return 1
    if r == 1:
        return n

    numer = [n - r + k + 1 for k in range(r)]
    denom = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denom[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numer[k - offset] /= pivot
                denom[k] /= pivot

    result = 1
    for k in range(r):
        if numer[k] > 1:
            result *= int(numer[k])

    return result


def solve(p: int, a: "List[int]"):
    b = [0]*p
    for ai, av in enumerate(a):
        if av == 1:
            for i in range(p):
                b[i] += -cmb(p-1, i) * (-ai)**(p-i-1)
                b[i] %= p
            b[0] += 1
            b[0] %= p
    print(*b, sep=" ")
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    p = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(p-1-0+1)]  # type: "List[int]"
    solve(p, a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

p = int(input())
aaa = list(map(int, input().split()))

bins = [1]
for i in range(1, p):
    bins.append(bins[-1] * (p - i) * pow(i, p - 2, p) % p)
bins = np.array(bins, dtype=np.int32)

coefs = np.zeros(p, dtype=np.int32)

for i, a in enumerate(aaa):
    if a == 0:
        continue

    coefs[0] += 1

    pows = [1]
    for _ in range(1, p):
        pows.append(pows[-1] * -i % p)
    pows.reverse()
    pows = np.array(pows, dtype=np.int32)

    coefs = (coefs - bins * pows) % p

print(*coefs)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

p = int(input())
aaa = list(map(int, input().split()))

q = p - 2
m = np.arange(p + 1, dtype=np.int32)
r = np.ones(p + 1, dtype=np.int32)
while q:
    if q & 1:
        r = r * m % p
    m = m * m % p
    q >>= 1

coefs = [0] * p
coefs[0] = sum(aaa)
for i, a in enumerate(aaa):
    if a == 0:
        continue
    b = 1
    for j in range(p - 1, -1, -1):
        coefs[j] = (coefs[j] - b) % p
        b = -b * i * j * r[p - j] % p

print(*coefs)

Submission status: Time Limit Exceeded

Solution code:
p = int(input())
aaa = list(map(int, input().split()))

coefs = [0] * p
coefs[0] = sum(aaa)
invs = [pow(x, p - 2, p) for x in range(p + 1)]
for i, a in enumerate(aaa):
    if a == 0:
        continue
    b = 1
    for j in range(p - 1, -1, -1):
        coefs[j] = (coefs[j] - b) % p
        b = -b * i * j * invs[p - j] % p

print(*coefs)

Submission status: Time Limit Exceeded

Solution code:
p = int(input())
aaa = list(map(int, input().split()))

coefs = [0] * p
coefs[0] = sum(aaa)
invs = [pow(x, p - 2, p) for x in range(p + 1)]
for i, a in enumerate(aaa):
    if a == 0:
        continue

    b = 1
    c = 1
    for j in range(p - 1, -1, -1):
        coefs[j] = (coefs[j] - b * c) % p
        b = -b * i % p
        c = c * j * invs[p - j] % p

print(*coefs)

Submission status: Time Limit Exceeded

Solution code:
p = int(input())
a_list = list(map(int, input().split()))
r_list = [0] * p

fact = [0] * p
fact[0] = 1
for i in range(1, p):
    fact[i] = fact[i - 1] * i % p

fact_inv = [pow(fact[i], p-2, p) for i in range(p)]

ncr = [(fact[p-1] * fact_inv[p-1-i] * fact_inv[i]) % p for i in range(p)]

for j in range(p):
    if a_list[j] == 0:
        continue
    for i in range(p):
        s = (ncr[i] * pow(-j, p-1-i, p)) % p
        r_list[i] -= s
    r_list[0] += 1


print(" ".join([str(r % p) for r in r_list]))

Submission status: Time Limit Exceeded

Solution code:
p = int(input())
a_list = list(map(int, input().split()))
r_list = [0] * p

fact = [0] * p
fact[0] = 1
for i in range(1, p):
    fact[i] = fact[i - 1] * i % p

fact_inv = [pow(fact[i], p-2, p) for i in range(p)]

for j in range(p):
    if a_list[j] == 0:
        continue
    for i in range(p):
        s = fact[p-1] * fact_inv[p-1-i] * fact_inv[i] * pow(-j, p-1-i, p)
        s = s % p
        r_list[i] -= s
    r_list[0] += 1


print(" ".join([str(r % p) for r in r_list]))

Submission status: Time Limit Exceeded

Solution code:
p=int(input())
A=tuple(map(int,input().split()))

Fact=[1]
for i in range(1,p):
    Fact.append(Fact[i-1]*i%p)
Finv=[0]*p
Finv[-1]=pow(Fact[-1],p-2,p)
for i in range(p-2,-1,-1):
    Finv[i]=Finv[i+1]*(i+1)%p
def comb(n,r):
    if n<r:
        return 0
    return Fact[n]*Finv[r]*Finv[n-r]%p

B=[0]*p
B[0]=sum(A)
for i,a in enumerate(A):
    if a:
        for j in range(p):
            B[j]+=-comb(p-1,j)*pow(-i,p-1-j,p)
            B[j]%=p
print(*B)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    print(max(a+b,a-b,a*b))
    return

#B
def B():
    k,x = LI()
    ans = []
    for i in range(x-k+1,x+k):
        ans.append(i)
    print(*ans)
    return

#C
def C():
    def f(s):
        res = [0]*m
        for i in s:
            res[alp.index(i)] += 1
        return res
    alp = list("abcdefghijklmnopqrstuvwxyz")
    m = len(alp)
    n = I()
    s = [input() for i in range(n)]
    d = defaultdict(lambda : 0)
    for i in s:
        d[tuple(f(i))] += 1
    ans = 0
    for i in d.values():
        ans += (i*(i-1))//2
    print(ans)
    return

#D
def D():
    n,m = LI()
    g = LIR(n)
    g.sort(key = lambda x:x[0])
    ans = 0
    f = [1]*n
    j = 0
    q = []
    for i in range(m)[::-1]:
        while j < n and m-g[j][0] >= i:
            a,b = g[j]
            heappush(q,(-b,a))
            j += 1
        if q:
            x,a = heappop(q)
            if i+a <= m:
                ans -= x
    print(ans)
    return

#E
def E():
    def dfs(x,f):
        for y,w in v[x]:
            if f[y]:
                if dp[y] < dp[x]+w:
                    f[y] = 0
                    dp[y] = dp[x]+w
                    dfs(y,f)
                    f[y] = 1
            else:
                if dp[y] < dp[x]+w:
                    dp[y] = float("inf")
                    dfs(y,f)
    n,m,p = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b,c = LI()
        a -= 1
        b -= 1
        v[a].append((b,c-p))
    f = [1]*n
    dp = [-float("inf")]*n
    dp[0] = 0
    f[0] = 0
    dfs(0,f)
    ans = dp[n-1]
    if ans == float("inf") or ans == -float("inf"):
        print(-1)
    elif ans < 0:
        print(0)
    else:
        print(ans)
    return

#F
def F():
    def comb(a,b):
        return fact[a]*inv[b]*inv[a-b]%p

    p = I()
    a = LI()
    fact = [1]
    for i in range(p-1):
        fact.append(fact[-1]*(i+1)%p)
    inv = [1]*p
    inv[p-1] = pow(fact[p-1],p-2,p)
    for i in range(1,p)[::-1]:
        inv[i-1] = inv[i]*i%p
    b = [0]*p
    for i in range(p):
        ai = a[i]
        if ai:
            b[0] += ai
            for j in range(p):
                c = ai*comb(p-1,j)*pow(i,p-1-j,p)%p
                if j%2:
                    b[j] += c
                else:
                    b[j] -= c
                b[j] %= p
    print(*b)
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    print(max(a+b,a-b,a*b))
    return

#B
def B():
    k,x = LI()
    ans = []
    for i in range(x-k+1,x+k):
        ans.append(i)
    print(*ans)
    return

#C
def C():
    def f(s):
        res = [0]*m
        for i in s:
            res[alp.index(i)] += 1
        return res
    alp = list("abcdefghijklmnopqrstuvwxyz")
    m = len(alp)
    n = I()
    s = [input() for i in range(n)]
    d = defaultdict(lambda : 0)
    for i in s:
        d[tuple(f(i))] += 1
    ans = 0
    for i in d.values():
        ans += (i*(i-1))//2
    print(ans)
    return

#D
def D():
    n,m = LI()
    g = LIR(n)
    g.sort(key = lambda x:x[0])
    ans = 0
    f = [1]*n
    j = 0
    q = []
    for i in range(m)[::-1]:
        while j < n and m-g[j][0] >= i:
            a,b = g[j]
            heappush(q,(-b,a))
            j += 1
        if q:
            x,a = heappop(q)
            if i+a <= m:
                ans -= x
    print(ans)
    return

#E
def E():
    def dfs(x,f):
        for y,w in v[x]:
            if f[y]:
                if dp[y] < dp[x]+w:
                    f[y] = 0
                    dp[y] = dp[x]+w
                    dfs(y,f)
                    f[y] = 1
            else:
                if dp[y] < dp[x]+w:
                    dp[y] = float("inf")
                    dfs(y,f)
    n,m,p = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b,c = LI()
        a -= 1
        b -= 1
        v[a].append((b,c-p))
    f = [1]*n
    dp = [-float("inf")]*n
    dp[0] = 0
    f[0] = 0
    dfs(0,f)
    ans = dp[n-1]
    if ans == float("inf") or ans == -float("inf"):
        print(-1)
    elif ans < 0:
        print(0)
    else:
        print(ans)
    return

#F
def F():
    def comb(a,b):
        return fact[a]*inv[b]*inv[a-b]%p

    p = I()
    a = LI()
    fact = [1]
    for i in range(p-1):
        fact.append(fact[-1]*(i+1)%p)
    inv = [1]*p
    inv[p-1] = pow(fact[p-1],p-2,p)
    for i in range(1,p)[::-1]:
        inv[i-1] = inv[i]*i%p
    b = [0]*p
    for i in range(p):
        ai = a[i]
        if ai:
            b[0] += ai
            for j in range(p):
                b[j] -= (-1)**(j%2)*ai*comb(p-1,j)*pow(i,p-1-j,p)%p
                b[j] %= p
    print(*b)
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    print(max(a+b,a-b,a*b))
    return

#B
def B():
    k,x = LI()
    ans = []
    for i in range(x-k+1,x+k):
        ans.append(i)
    print(*ans)
    return

#C
def C():
    def f(s):
        res = [0]*m
        for i in s:
            res[alp.index(i)] += 1
        return res
    alp = list("abcdefghijklmnopqrstuvwxyz")
    m = len(alp)
    n = I()
    s = [input() for i in range(n)]
    d = defaultdict(lambda : 0)
    for i in s:
        d[tuple(f(i))] += 1
    ans = 0
    for i in d.values():
        ans += (i*(i-1))//2
    print(ans)
    return

#D
def D():
    n,m = LI()
    g = LIR(n)
    g.sort(key = lambda x:x[0])
    ans = 0
    f = [1]*n
    j = 0
    q = []
    for i in range(m)[::-1]:
        while j < n and m-g[j][0] >= i:
            a,b = g[j]
            heappush(q,(-b,a))
            j += 1
        if q:
            x,a = heappop(q)
            if i+a <= m:
                ans -= x
    print(ans)
    return

#E
def E():
    def dfs(x,f):
        for y,w in v[x]:
            if f[y]:
                if dp[y] < dp[x]+w:
                    f[y] = 0
                    dp[y] = dp[x]+w
                    dfs(y,f)
                    f[y] = 1
            else:
                if dp[y] < dp[x]+w:
                    dp[y] = float("inf")
                    dfs(y,f)
    n,m,p = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b,c = LI()
        a -= 1
        b -= 1
        v[a].append((b,c-p))
    f = [1]*n
    dp = [-float("inf")]*n
    dp[0] = 0
    f[0] = 0
    dfs(0,f)
    ans = dp[n-1]
    if ans == float("inf") or ans == -float("inf"):
        print(-1)
    elif ans < 0:
        print(0)
    else:
        print(ans)
    return

#F
def F():
    def comb(a,b):
        return fact[a]*inv[b]*inv[a-b]%p

    p = I()
    a = LI()
    fact = [1]
    for i in range(p-1):
        fact.append(fact[-1]*(i+1)%p)
    inv = [1]*p
    inv[p-1] = pow(fact[p-1],p-2,p)
    for i in range(1,p)[::-1]:
        inv[i-1] = inv[i]*i%p
    b = [0]*p
    po = [[pow(i,j,p) for j in range(p)] for i in range(p)]
    for i in range(p):
        ai = a[i]
        b[0] += ai
        for j in range(p):
            b[j] -= (-1)**(j%2)*ai*comb(p-1,j)*po[i][p-1-j]%p
            b[j] %= p
    print(*b)
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
# from Crypto.Util.number import inverse
def inverse(t,l):
    return pow(t,l-2,l)
xy = []

class Polynomial(list):

    def __init__(self,coeffs):
        self.coeffs = coeffs

    def evaluate(self,x,mod):
        val = 0
        for i in range(len(self.coeffs)):
            val = (val + x**i * self.coeffs[i]) % mod
        return val

    def raise_degree(self,x):
        coeffs=[]

        for i in range(x):
            coeffs.append(0)
        for i in range(len(self.coeffs)):
            coeffs.append(self.coeffs[i])
        self.coeffs=coeffs

    def add_to_degree(self,x,y):
        while(len(self.coeffs)<=x):
            self.coeffs.append(0)
        self.coeffs[x]=(self.coeffs[x]+y)%MOD

    def add_poly(self,x):
        while(len(self.coeffs)<len(x.coeffs)):
            self.coeffs.append(0)

        for i in range(len(x.coeffs)):
            self.coeffs[i]=(self.coeffs[i]+x.coeffs[i])%MOD

    def multiply(self,x):
        for i in range(len(self.coeffs)):
            self.coeffs[i]=(self.coeffs[i] * x)%MOD

    def multiply_with_poly(self,p):
        coeffs=Polynomial([])

        for i in range(len(self.coeffs)):
            q=Polynomial(p.coeffs)
            q.raise_degree(i)
            q.multiply(self.coeffs[i])
            coeffs.add_poly(q)
        self.coeffs=coeffs.coeffs

    def calculate_derivative(self):
        p=Polynomial([])
        for i in range(1,len(self.coeffs)):
            p.coeffs.append((self.coeffs[i]*i)%MOD)
        return p

    def compose(self,p):
        P=Polynomial([])
        q=Polynomial([1])
        for i in range(len(self.coeffs)):
            q2=Polynomial(q.coeffs)
            q2.multiply(self.coeffs[i])
            P.add_poly(q2)
            q.multiply_with_poly(p)
        self.coeffs=P.coeffs

    def print_poly(self):
        return self.coeffs

#Lagrange Interpolation part
def Lagrange_Basis_Polynomial(xlist,index):
    l=Polynomial([1])
    for i in range(len(xlist)):
        if(i==index):
            continue
        p=Polynomial([(MOD-xlist[i])%MOD,1])
        p.multiply(inverse((MOD+xlist[index]-xlist[i])%MOD,MOD))
        l.multiply_with_poly(p)
    return l

def Lagrange_Polynomial(xylist):
    xlist=[]
    ylist=[]
    L=Polynomial([])
    for a in xylist:
        xlist.append(a[0])
        ylist.append(a[1])
    for i in range(len(ylist)):
        l=Lagrange_Basis_Polynomial(xlist,i)
        l.multiply(ylist[i])
        L.add_poly(l)
    return L
 
MOD = int(input())
arr = [int(x) for x in input().split()]
xy=[]
for i in range(len(arr)):
    xy.append((i,arr[i]))
coeffs = Lagrange_Polynomial(xy).print_poly()
for i in coeffs:
    print(i,end=" ")

Submission status: Time Limit Exceeded

Solution code:

# from Crypto.Util.number import inverse
def inverse(t,l):
    return pow(t,l-2,l)
xy = []

class Polynomial(list):

    def __init__(self,coeffs):
        self.coeffs = coeffs

    def evaluate(self,x,mod):
        val = 0
        for i in range(len(self.coeffs)):
            val = (val + x**i * self.coeffs[i]) % mod
        return val

    def raise_degree(self,x):
        coeffs=[]

        for i in range(x):
            coeffs.append(0)
        for i in range(len(self.coeffs)):
            coeffs.append(self.coeffs[i])
        self.coeffs=coeffs

    def add_to_degree(self,x,y):
        while(len(self.coeffs)<=x):
            self.coeffs.append(0)
        self.coeffs[x]=(self.coeffs[x]+y)%MOD

    def add_poly(self,x):
        while(len(self.coeffs)<len(x.coeffs)):
            self.coeffs.append(0)

        for i in range(len(x.coeffs)):
            self.coeffs[i]=(self.coeffs[i]+x.coeffs[i])%MOD

    def multiply(self,x):
        for i in range(len(self.coeffs)):
            self.coeffs[i]=(self.coeffs[i] * x)%MOD

    def multiply_with_poly(self,p):
        coeffs=Polynomial([])

        for i in range(len(self.coeffs)):
            q=Polynomial(p.coeffs)
            q.raise_degree(i)
            q.multiply(self.coeffs[i])
            coeffs.add_poly(q)
        self.coeffs=coeffs.coeffs

    def calculate_derivative(self):
        p=Polynomial([])
        for i in range(1,len(self.coeffs)):
            p.coeffs.append((self.coeffs[i]*i)%MOD)
        return p

    def compose(self,p):
        P=Polynomial([])
        q=Polynomial([1])
        for i in range(len(self.coeffs)):
            q2=Polynomial(q.coeffs)
            q2.multiply(self.coeffs[i])
            P.add_poly(q2)
            q.multiply_with_poly(p)
        self.coeffs=P.coeffs

    def print_poly(self):
        return self.coeffs

#Lagrange Interpolation part
def Lagrange_Basis_Polynomial(xlist,index):
    l=Polynomial([1])
    for i in range(len(xlist)):
        if(i==index):
            continue
        p=Polynomial([(MOD-xlist[i])%MOD,1])
        p.multiply(inverse((MOD+xlist[index]-xlist[i])%MOD,MOD))
        l.multiply_with_poly(p)
    return l

def Lagrange_Polynomial(xylist):
    xlist=[]
    ylist=[]
    L=Polynomial([])
    for a in xylist:
        xlist.append(a[0])
        ylist.append(a[1])
    for i in range(len(ylist)):
        l=Lagrange_Basis_Polynomial(xlist,i)
        l.multiply(ylist[i])
        L.add_poly(l)
    return L

MOD=int(raw_input())
arr=map(int,raw_input().split())
xy=[]
for i in range(len(arr)):
    xy.append((i,arr[i]))
# print(xy)
coeffs = Lagrange_Polynomial(xy).print_poly()
for i in coeffs:
    print i,

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
import itertools

P = int(input())
A = [int(x) for x in input().split()]

P,A

one = np.array([1], dtype=np.int64)
arr = [np.array([(-x)%P,1],dtype=np.int64) for x in range(P)]
L = [one] + list(itertools.accumulate(arr[:-1],lambda a,b: np.convolve(a,b) % P))
R = ([one] + list(itertools.accumulate(arr[1:][::-1],lambda a,b: np.convolve(a,b) % P)))[::-1]
X = [np.convolve(A,B) % P for A,B in zip(L,R)]

f = np.zeros(P,dtype=np.int64)
for a,x in zip(A,X):
    if a == 1:
        f -= x

f %= P
print(*f)

Submission status: Accepted

Solution code:
#fin=open('in','r')
#input=lambda:fin.readline().strip()

p=int(input())
fact=[0]*p
inv=[0]*p
def f(x,m=p-2):
	ans=1
	while m:
		if m&1:ans=ans*x%p
		x=x*x%p
		m>>=1
	return ans
fact[0]=inv[0]=1
for i in range(1,p):
	fact[i]=fact[i-1]*i%p
	inv[i]=inv[i-1]*f(i)%p
r=list(map(int,input().split()))
c=[i for i in range(p) if r[i] == 1]
#sum of -((x-j)^(p-1)-1)
# (-j + x)^(p-1) = sum((-j)^i * x^(p-1-i) * binom(p-1,i))
coeff=[0]*p
for j in c:
	for i in range(p-1,-1,-1):
		if i&1:coeff[p-1-i]+=fact[p-1]*inv[i]*inv[p-1-i]*f(j,i)%p
		else:coeff[p-1-i]-=fact[p-1]*inv[i]*inv[p-1-i]*f(j,i)%p
	coeff[0]+=1
coeff=[(t%p+p)%p for t in coeff]
print(*coeff)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


p = int(input())
a = list(map(int, input().split()))

### 素数の逆元とCombination

M = p
N = 10**4 # 必要なテーブルサイズ

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 

def cmb(n, r, M):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return (g1[n] * g2[r] * g2[n-r]) % M
ans = [0]*p
for i,num in enumerate(a):
    if num==0:
        continue
    val = 1
    for j in reversed(range(p)):
        ans[j] += -cmb(p-1,j,M) * val #pow(-i,p-1-j,M)
#         ans[j] += -cmb(p-1,j,M) * pow(-i,p-1-j,M)
        ans[j] %= M
        val *= -i
        val %= M
    ans[0] += 1
for i in range(p):
    ans[i] %= M
write(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


p = int(input())
a = list(map(int, input().split()))

### 素数の逆元とCombination

M = p
N = 10**4 # 必要なテーブルサイズ

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 

def cmb(n, r, M):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return (g1[n] * g2[r] * g2[n-r]) % M
ans = [0]*p
for i,num in enumerate(a):
    if num==0:
        continue
    for j in range(p):
        ans[j] += -cmb(p-1,j,M) * pow(-i,p-1-j,M)
        ans[j] %= M
    ans[0] += 1
for i in range(p):
    ans[i] %= M
write(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
#mod = 10**9+7 #998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    p = int(ipt())
    a = [int(i) for i in ipt().split()]
    mod = p
    #nCrをmodで割った余りを求める。Nに最大値を入れて使用。
    N = 3000
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル
    def cmb(n,r,mod=p):
        if r<0 or r>n :
            return 0
        r = min(r,n-r)
        return g1[n]*g2[r]*g2[n-r]%mod
    for i in range(2,N+1):
        g1.append((g1[-1]*i)%mod)
        inverse.append((-inverse[mod % i]*(mod//i))%mod)
        g2.append((g2[-1]*inverse[-1])%mod)

    ans = [0]*p
    for i in range(p):
        if a[i]:
            ans[0] += 1
            sgn = -1
            ji = 1
            for j in range(p-1,-1,-1):
                ans[j] += sgn*ji*cmb(p-1,j,p)
                ji *= i
                ji %= p
                ans[j] %= p
                sgn *= -1

    print(" ".join(map(str,ans)))
    return None

if __name__ == '__main__':
    main()