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

Solution (Python):



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]


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)

Solution (Python):
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()))



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

        ans[j] %= M
        val *= -i
        val %= M
    ans[0] += 1
for i in range(p):
    ans[i] %= M
write(" ".join(map(str, ans)))

Solution (Python):
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()))



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 
    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)))

Solution (Python):
'''
研究室PCでの解答
'''
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

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
    
    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()

Solution (Python):
import numpy as np
mod = 998244353

def poly_mul(f, g):
    
    Lf = len(f); Lg = len(g); L = Lf + Lg - 1
    if Lf <= 16 or Lg <= 16:
        if Lf == 0 or Lg == 0:
            return np.zeros((0,), dtype=np.int64)
        return (np.convolve(f.astype(np.uint64), g.astype(np.uint64)) % mod).astype(np.int64)
    fft = np.fft.rfft; ifft = np.fft.irfft
    fft_len = 1 << L.bit_length()
    fl = f & (1 << 15) - 1; fh = f >> 15
    gl = g & (1 << 15) - 1; gh = g >> 15
    x = (ifft(fft(fl, fft_len) * fft(gl, fft_len))[:L] + 0.5).astype(np.int64) % mod
    y = (ifft(fft(fl+fh, fft_len) * fft(gl+gh, fft_len))[:L] + 0.5).astype(np.int64) % mod
    z = (ifft(fft(fh, fft_len) * fft(gh, fft_len))[:L] + 0.5).astype(np.int64) % mod
    return (x + ((y - x - z) << 15) + (z << 30)) % mod

def poly_inv(fps, n=None):
    assert fps[0] != 0
    if n is None:
        n = len(fps)
    res = np.zeros(1<<(n-1).bit_length(), dtype=np.int64)
    res[0] = pow(int(fps[0]), mod-2, mod)
    i = 1
    while i < n:
        i <<= 1
        res[:i] = ((res[:i]<<1) - poly_mul(poly_mul(res[:i>>1], res[:i>>1]), fps[:i])[:i]) % mod
    return res[:n]

def poly_div(fps1, fps2):
    n1, n2 = len(fps1), len(fps2)
    if n1 < n2:
        return np.zeros((0,), dtype=np.int64)
    n = n1 - n2 + 1
    res = poly_mul(fps1[-1:-n-1:-1], poly_inv(fps2[::-1], n))[n-1::-1]
    return res

def poly_mod(fps1, fps2):
    n1, n2 = len(fps1), len(fps2)
    if n1 < n2:
        return fps1
    res = fps1[:n2-1] - poly_mul(poly_div(fps1, fps2), fps2)[:n2-1]
    return res % mod

def multipoint_evaluation(fps, xs):
    threshold = 8
    n_xs = len(xs)
    bit = (n_xs-1).bit_length()
    if bit <= threshold:
        res = np.zeros_like(xs)
        xs_cumprod = np.ones_like(xs)
        for coef in fps:
            res += xs_cumprod * coef
            xs_cumprod *= xs
            xs_cumprod %= mod
        return res
    k = 1<<bit
    fpss = np.zeros((bit+1, k+1), dtype=fps.dtype)
    fpss[0, :n_xs] = -xs % mod
    fpss[1, :k:2] = fpss[0, :k:2] * fpss[0, 1::2] % mod
    fpss[1, 1::2] = (fpss[0, :k:2] + fpss[0, 1::2]) % mod
    for i in range(1, bit):
        step = 2<<i
        half = step>>1
        for j in range(0, k, step):
            f1 = fpss[i, j:j+half+1].copy()
            f2 = fpss[i, j+half:j+step+1].copy()
            f1[-1] = f2[-1] = 1
            f = poly_mul(f1, f2)
            fpss[i+1, j:j+step] = f[:-1]
    f = poly_mod(fps, f)
    fpss[-1, :len(f)] = f
    fpss[-1, len(f):] = 0
    for i in range(bit-1, threshold-1, -1):
        step = 2<<i
        half = step>>1
        for j in range(0, k, step):
            f = fpss[i+1, j:j+step]
            f1 = fpss[i, j:j+half+1].copy()
            f2 = fpss[i, j+half:j+step+1].copy()
            f1[-1] = f2[-1] = 1
            fpss[i, j:j+half] = poly_mod(f, f1)
            fpss[i, j+half:j+step] = poly_mod(f, f2)
    xs = (-fpss[0, :k] % mod).reshape(-1, 1<<threshold)
    xs_cumprod = np.ones_like(xs)
    res = np.zeros_like(xs)
    for i in range(1<<threshold):
        res += fpss[threshold, i:k:1<<threshold, None] * xs_cumprod % mod
        xs_cumprod *= xs
        xs_cumprod %= mod
    return res.reshape(-1)[:n_xs] % mod

def poly_differential(fps):
    return fps[1:] * np.arange(1, len(fps)) % mod

def lagrange_interpolation(X, Y, mod):
    
    n = len(X)
    g = [0]*(n+1)
    g[0] = 1
    for i, x in enumerate(X):
        for j in range(i, -1, -1):
            g[j+1] += g[j] * (-x) % mod
    res = [0]*n
    for x, y in zip(X, Y):
        f = g[:]
        denom = 0
        v = 1
        pow_x = [1]  
        for _ in range(n-1):
            v = v * x % mod
            pow_x.append(v)
        pow_x.reverse()  
        for i, po in enumerate(pow_x):
            f_i = f[i]
            f[i+1] += f_i * x % mod  
            denom = (denom + f_i * po) % mod
        denom_inv = pow(denom, mod-2, mod)
        for i, f_i in enumerate(f[:n]):
            res[i] += (f_i * y * denom_inv)
    return [v % mod for v in res]

def polynomial_interpolation(xs, ys):
    
    assert len(xs) == len(ys)
    threshold = 8
    as_strided = np.lib.stride_tricks.as_strided
    n = len(xs)
    if n==1:
        return ys.copy()
    bit = (n-1).bit_length()
    if bit <= threshold:
        res = lagrange_interpolation(xs.tolist(), ys.tolist(), mod)
        return np.array(res[::-1], dtype=np.int64)
    k = 1<<bit
    fpss = np.zeros((bit+1, n+1), dtype=np.int64)
    fpss[0, :n] = -xs % mod
    for i in range(bit):
        step = 2 << i
        half = step >> 1
        for j in range(0, n, step):
            if j+half >= n:
                fpss[i+1, j:n] = fpss[i, j:n]
                continue
            f1 = fpss[i, j:j+half+1].copy()
            f2 = fpss[i, j+half:j+step+1].copy()
            f1[-1] = f2[-1] = 1
            f = poly_mul(f1, f2)
            fpss[i+1, j:j+len(f)-1] = f[:-1]
    fpss2 = np.zeros((bit+1, k+1), dtype=np.int64)
    fpss2[bit, :n] = poly_differential(f)
    for i in range(bit-1, threshold-1, -1):
        step = 2<<i
        half = step>>1
        for j in range(0, n, step):
            if j+half >= n:
                fpss2[i, j:n] = fpss2[i+1, j:n]
                continue
            f = fpss2[i+1, j:min(j+step, n)]
            f1 = fpss[i, j:j+half+1].copy()
            f2 = fpss[i, j+half:min(j+step, n)+1].copy()
            f1[-1] = f2[-1] = 1
            fpss2[i, j:j+half] = poly_mod(f, f1)
            fpss2[i, j+half:min(j+step, n)] = poly_mod(f, f2)
    xs = as_strided(xs, (k>>threshold, 1<<threshold), (8<<threshold, 8))
    xs_cumprod = np.ones_like(xs)
    f = np.zeros_like(xs)
    for i in range(1<<threshold):
        f += fpss2[threshold, i:k:1<<threshold, None] * xs_cumprod % mod
        xs_cumprod *= xs
        xs_cumprod %= mod
    f = f.ravel()
    for j in range(n):
        fpss2[0, j] = ys[j] * pow(int(f[j]), mod-2, mod) % mod
    for i in range(bit):
        step = 2 << i
        half = step >> 1
        for j in range(0, k, step):
            if j+half >= n:
                fpss2[i+1, j:n] = fpss2[i, j:n]
                continue
            f1 = fpss[i, j:j+half+1].copy()
            f2 = fpss[i, j+half:j+step+1].copy()
            f1[-1] = f2[-1] = 1
            fpss2[i+1, j:min(j+step, n)] = (
                poly_mul(fpss2[i, j:j+half], f2)
                + poly_mul(fpss2[i, j+half:min(j+step, n)], f1)
            ) % mod
    return fpss2[bit, :n]

mod = int(input())
A = np.array(input().split(), dtype=np.int64)
X = np.arange(mod, dtype=np.int64)
Ans = polynomial_interpolation(X, A)
print(" ".join(map(str, Ans.tolist())))

Solution (Python):


def lagrange_interpolation(X, Y, mod):
    
    
    n = len(X)
    g = [0]*(n+1)
    g[0] = 1
    for i, x in enumerate(X):
        for j in range(i, -1, -1):
            g[j+1] += g[j] * (-x) % mod
    res = [0]*n
    for x, y in zip(X, Y):
        f = g[:]
        denom = 0
        v = 1
        pow_x = [1]  
        for _ in range(n-1):
            v = v * x % mod
            pow_x.append(v)
        pow_x.reverse()  
        for i, po in enumerate(pow_x):
            f_i = f[i]
            f[i+1] += f_i * x % mod  
            denom = (denom + f_i * po)
        denom_inv = pow(denom, mod-2, mod)
        for i, f_i in enumerate(f[:n]):
            res[i] += (f_i * y * denom_inv)
    return [v % mod for v in res]

p = int(input())
A = list(map(int, input().split()))
ans = lagrange_interpolation(list(range(p)), A, p)
print(" ".join(map(str, ans[::-1])))

Solution (Python):
P = int(input())
A = list(map(int, input().split()))

Q = [1 for _ in range(P)]

for i in range(P):
    if A[i]:
        for k in range(P):
            if i == k:
                continue
            Q[i] *= (i - k)
            Q[i] %= P
        Q[i] = pow(Q[i], P - 2, P)
    else:
        Q[i] = 0

F = [0 for _ in range(P + 1)]
F[0] = 1

for i in range(P):
    tmp = [0 for _ in range(P + 1)]
    for j in range(1, P + 1):
        tmp[j] += F[j - 1]
        tmp[j] %= P
    for j in range(P + 1):
        tmp[j] += F[j] * (-i)
        tmp[j] %= P
    F = tmp

res = [0 for _ in range(P)]

for i in range(P):
    G = [0 for _ in range(P)]
    G[P - 1] = F[P]
    res[P - 1] += Q[i] * G[P - 1]
    res[P - 1] %= P
    for j in range(P - 1)[::-1]:
        G[j] = F[j + 1] + i * G[j + 1]
        G[j] %= P
        res[j] += Q[i] * G[j]
        res[j] %= P

print(*res)

Solution (Python):
class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def C(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def P(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod


P = int(input())
c = Combi(P-1, P)
A = list(map(int,input().split()))
power=[1 for i in range(P)]
ans = [0 for i in range(P)]
for i in range(P):
    if A[i] != 0:
        ans[0] += 1
        power[0]
        for  _ in range(1,P):
            power[_]=power[_-1]*(-i)%P
        for j in range(P):
            ans[j] -= c.C(P-1, j)*power[P-1-j] 
for i in range(P):
    ans[i] %= P
print(*ans)

Solution (Python):
class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def C(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def P(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod


P = int(input())
c = Combi(P-1, P)
A = list(map(int,input().split()))
ans = [0 for i in range(P)]
for i in range(P):
    if A[i] != 0:
        ans[0] += 1
        for j in range(P):
            ans[j] -= c.C(P-1, j)*pow(-i, P-1-j,P) 
for i in range(P):
    ans[i] %= P
print(*ans)

Solution (Python):
def ext_euc(a, b):
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euc(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    x, _, _ = ext_euc(a, mod)
    return x % mod


def main():
    p = int(input())
    A = list(map(int, input().split()))
    
    comb = [1] * p
    for i in range(1, p):
        v = comb[i - 1]
        v *= p - i
        v *= mod_inv(i, p)
        comb[i] = v % p
    b = [0] * p
    for k, a in enumerate(A):
        if a == 0:
            continue
        pw = [1] * p  
        for i in range(1, p):
            pw[- (i + 1)] = (pw[- i] * (- k)) % p
        for i in range(p):
            if i == 0:
                b[i] += 1
            b[i] -= comb[i] * pw[i]
            b[i] %= p
    print(' '.join(map(str, b)))            


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush

from functools import reduce,lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): 
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    
    

    p = int(input())
    
    A = tuple(map(int, input().split())) 
    
    
    mod = p
    maxn=p
    fact=[1]*(maxn+1)
    invs=[1]*(maxn+1);invs[0]=0
    ifact=[1]*(maxn+1)
    for i in range(2,maxn+1):
        fact[i]=(fact[i-1]*i)%mod
        invs[i]=invs[mod%i]*(-(mod//i))%mod
        ifact[i]=(ifact[i-1]*invs[i])%mod
    def perm(n,r): return fact[n]*ifact[n-r]%mod
    def comb(n,r): return (fact[n]*ifact[r]%mod)*ifact[n-r]%mod
    def multicomb(self,n,*rs):
        ans=fact[n]
        for r in rs: ans=(ans*self.ifact[r])%self.mod
        return ans
    
    tot=[0]*p
    tot[0]=sum(A)%mod
    for i in range(p):
        a=A[i]
        if not a:
            continue
        
        mi=(-i)%mod
        base=pow(mi,p-1,mod)
        
        for j in range(p):
            if j==p-1:
                base=1
            tot[j]-=base*comb(p-1,j)%mod
            tot[j]%=mod
            base*=invs[mi]
            base%=mod

    
    print(*tot)


if __name__ == "__main__":
    main()

Solution (Python):
p=int(input())
alist=list(map(int,input().split()))

fact_list=[1]
fact_inv_list=[1]
for i in range(1,p):
  fact=(fact_list[-1]*i)%p
  fact_list.append(fact)
  fact_inv_list.append(pow(fact,p-2,p))
def comb_mod(n,r):
  return fact_list[n]*fact_inv_list[r]*fact_inv_list[n-r]
  
answer_list=[0]*p
for i in range(p):
  a=alist[i]
  if a==1:
    
    coeff_list=[0]*p
    coeff_list[0]=1
    for j in range(p):
      coeff_list[j]-=comb_mod(p-1,j)*pow(-i,p-1-j,p)
      
    
    for i in range(p):
      answer_list[i]+=coeff_list[i]
      
for i in range(p):
  answer_list[i]%=p

print(*answer_list)

Solution (Python):
p=int(input())
alist=list(map(int,input().split()))

fact_list=[1]
fact_inv_list=[1]
for i in range(1,p):
  fact=(fact_list[-1]*i)%p
  fact_list.append(fact)
  fact_inv_list.append(pow(fact,p-2,p))
def comb_mod(n,r):
  return fact_list[n]*fact_inv_list[r]*fact_inv_list[n-r]
  
answer_list=[0]*p
for i in range(p):
  a=alist[i]
  if a==1:
    
    coeff_list=[0]*p
    coeff_list[0]=1
    for j in range(p):
      coeff=comb_mod(p-1,j)*pow(-i,p-1-j,p)
      coeff_list[j]-=coeff
      coeff_list[j]%=p
      
    
    for i in range(p):
      answer_list[i]+=coeff_list[i]
      answer_list[i]%=p
      
print(*answer_list)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
p = int(readline())
a = list(map(int,readline().split()))

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

inv = [1]*(MAX+1)
for i in range(2, MAX+1):
    inv[i] = inv[p % i]*(p-p//i) % p

fact_inv = [1]*(MAX+1)
for i in range(1, MAX+1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % p

def comb(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[n-k] * fact_inv[k] % p

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

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

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

inv = [1]*(MAX+1)
for i in range(2, MAX+1):
    inv[i] = inv[p % i]*(p-p//i) % p

fact_inv = [1]*(MAX+1)
for i in range(1, MAX+1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % p

def comb(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[n-k] * fact_inv[k] % p

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

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

MOD = p
MAX = p + 10
fact = [1] * (MAX + 1)  
finv = [1] * (MAX + 1)  
iinv = [1] * (MAX + 1)  
for i in range(2, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * iinv[i] % MOD


def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n - k] % MOD


b = [0] * p
for j in range(p):
    if a[j] == 1:
        b[0] += 1
        for k in range(p):
            b[k] += comb(p - 1, k) * pow(j, p - 1 - k, MOD) * (-1)**(
                (p - k) % 2)
            b[k] %= MOD

print(*b)

Solution (Python):
import sys
input = sys.stdin.readline

p = int(input())
A = tuple(map(int, input().split()))
B = [0]*p
U = p-1
MOD = p
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z

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

Solution (Python):
P = int(input())
A = [int(_) for _ in input().split()]


class Factorial:
    def __init__(self, max_fact, mod):
        
        
        f = [1] * (max_fact + 1)
        for idx in range(2, max_fact + 1):
            f[idx] = f[idx - 1] * idx
            f[idx] %= mod
        fi = [pow(f[-1], mod - 2, mod)]
        for idx in range(max_fact, 0, -1):
            fi += [fi[-1] * idx % mod]
        fi = fi[::-1]
        self.mod = mod
        self.f = f
        self.fi = fi

    def factorial(self, n):
        return self.f[n]

    def factorial_inverse(self, n):
        return self.fi[n]

    def combination(self, n, r):
        f = self.f
        fi = self.fi
        return f[n] * fi[r] * fi[n - r] % self.mod

    def permutation(self, n, r):
        return self.f[n] * self.fi[n - r] % self.mod

    def homogeneous_product(self, n, r):
        f = self.f
        fi = self.fi
        return f[n + r - 1] * fi[r] * fi[n - 1] % self.mod


max_fact = P - 1
mod = P
fact_instance = Factorial(max_fact, mod)
comb = fact_instance.combination
perm = fact_instance.permutation
combrep = fact_instance.homogeneous_product

ans = [0] * P
for i, a in enumerate(A):
    if a:
        
        ans[0] += 1
        for r in range(P):
            ans[r] -= comb(P - 1, r) * pow(-i, P - 1 - r, P)
            ans[r] %= mod
print(*ans)

Solution (Python):
class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def inverse(self, k):
        """kの逆元を求める O(1)"""
        return (self.inv_fact[k] * self.fact[k - 1]) % self.MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

    def combination2(self, k, r):
        """kCrを求める O(r)
        kが大きいが、r <= nを満たしているときに使用
        """
        if k < r:
            return 0
        res = 1
        for l in range(r):
            res *= (k - l)
            res %= self.MOD
        return (res * self.inv_fact[r]) % self.MOD


p = int(input())
a = list(map(int, input().split()))
comb = Combination(p - 1, p)


b = [0] * p
for i in range(p):
    for j in range(p):
        
        tmp = pow(-j, (p - 1 - i), p) * comb.combination(p - 1, i)
        b[i] -= a[j] * tmp
        b[i] %= p
b[0] = a[0]

print(*b)

Solution (Python):
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  

p = I()
a = LI()




C = [1]
for i in range(1,p):
    C.append((C[-1]*(p-i)*pow(i,p-2,p)) % p)


ANS = [a[0]]
for i in range(1,p):
    s = -C[i] % p
    t = sum(a[j]*pow(-j,p-1-i,p) for j in range(p)) % p
    ANS.append((s*t) % p)

print(*ANS)

Solution (Python):
import sys
input = sys.stdin.readline


def main():
    P = int(input())
    A = list(map(int, input().split()))

    
    mod = P
    def cmb(n, r, mod=mod):
        if ( r<0 or r>n ):
            return 0
        r = min(r, n-r)
        return g1[n] * g2[r] * g2[n-r] % mod

    NN = 10**5 
    g1 = [1, 1] 
    g2 = [1, 1] 
    inverse = [0, 1] 

    for i in range( 2, NN + 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 j, a in enumerate(A):
        if a == 1:
            ans[0] = (ans[0] + 1) % P
            t = 1
            for k in range(P):
                ans[P-1-k] = (ans[P-1-k] - cmb(P-1, k) * t) % P
                t = t * (-j) % P
    print(*ans)


if __name__ == "__main__":
    main()

Solution (Python):
p = int(input())
a = list(map(int,input().split()))
mod = p
rng = 10100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def inv(x):
  return pow(x,mod-2,mod)
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
ans = [0]*p
for i in range(p):
  if a[i]:
    ans[0] += 1
    const = 1
    for j in range(p):
      ans[-j-1] -= ((-1)**(j%2))*cmb(p-1,j)*const
      ans[-j-1] %= mod
      const *= i
      const %= mod
print(*ans)

Solution (Python):
def modinv(x, mod):
    a, b = x, mod
    u, v = 1, 0
    while b:
        t = a // b
        a -= t * b; a, b = b, a
        u -= t * v; u, v = v, u
    return u % mod

def Lagrange_interpolation(X, Y, mod): 
    n = len(X) - 1
    for i in range(n+1):
        t = 1
        for j in range(n+1):
            if i != j:
                t = t * (X[i] - X[j]) % mod
        Y[i] = Y[i] * modinv(t, mod) % mod

    cur, nxt = 0, 1
    dp = [[0]*(n+2) for _ in range(2)]
    dp[0][0], dp[0][1] = -X[0], 1
    for i in range(1, n+1):
        for j in range(n+2):
            dp[nxt][j] = dp[cur][j] * -X[i] % mod
            if j:
                dp[nxt][j] = (dp[nxt][j] + dp[cur][j-1]) % mod
        cur, nxt = nxt, cur
    xinv = [modinv(v, mod) for v in X]
    ret = [0]*(n+1)
    for i in range(n+1):
        if Y[i] == 0:
            continue 
        if X[i] == 0:
            for j in range(n+1):
                ret[j] = (ret[j] + dp[cur][j+1] * Y[i]) % mod
        else:
            ret[0] = (ret[0] - dp[cur][0] * xinv[i] * Y[i]) % mod
            pre = -dp[cur][0] * xinv[i] % mod
            for j in range(1, n+1):
                ret[j] = (ret[j] - (dp[cur][j] - pre) * xinv[i] * Y[i]) % mod
                pre = (pre - dp[cur][j]) * xinv[i] % mod
    return ret

p = int(input())
a = list(map(int, input().split()))
x = list(range(p))
res = Lagrange_interpolation(x, a, p)
print(*res)

Solution (Python):
p = int(input())


def div(a, b):
    n = len(a)
    m = len(b)
    res = [0] * (n - m + 1)
    tmp = pow(b[-1], p - 2, p)
    for i in range(n - m, -1, -1):
        t = a[i + m - 1] * tmp % p
        res[i] = t
        for j in range(m):
            a[i + j] = (a[i + j] - t * b[j]) % p
    return res


a = list(map(int, input().split()))
ans = [0] * p
f = [0] * (p + 1)
f[0] = 1
for i in range(p):
    for j in range(p, 0, -1):
        f[j] += f[j - 1]
        f[j - 1] = -f[j - 1] * i
        f[j] %= p
for i in range(p):
    if a[i] == 1:
        fm = div(f[:], [-i, 1])
        t = 1
        r = 0
        for v in fm:
            r += v * t
            t = t * i % p
        t = pow(r, p - 2, p)
        for j in range(len(fm)):
            ans[j] += fm[j] * t
for i in range(p):
    ans[i] %= p
print(' '.join(map(str, ans)))

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.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

def solve():
    def lagrange_interpolation(x,y,mod=mod):
        n = len(x)-1
        dp = [0]*(n+2)
        dp[0] = x[0]
        dp[1] = 1
        for i in range(n):
            nd = [0]*(n+2)
            ni = i+1
            for j in range(n+2):
                nj = j
                nd[nj] += -x[ni]*dp[j]
                nd[nj] %= mod
                if j <= n:
                    nj = j+1
                    nd[nj] += dp[j]
                    nd[nj] %= mod
            for j in range(n+2):
                dp[j] = nd[j]

        f = [0]*(n+1)
        for i in range(n+1):
            if y[i] == 0:
                continue
            fi = 1
            for j in range(n+1):
                if i == j:
                    continue
                fi *= x[i]-x[j]
                fi %= mod
            fi = pow(fi,mod-2,mod)
            p = [0]*(n+1)
            if x[i] == 0:
                for j in range(n+1):
                    p[j] = dp[j+1]
            else:
                inv = pow(x[i],mod-2,mod)
                p[0] = -dp[0]*inv%mod
                for j in range(1,n+1):
                    p[j] = (p[j-1]-dp[j])*inv%mod
            for j in range(n+1):
                f[j] += y[i]*fi*p[j]
                f[j] %= mod
        return f
    p = I()
    a = LI()
    f = lagrange_interpolation(list(range(p)),a,p)
    print(*f)
    return


if __name__ == "__main__":
    solve()