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:
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
    for j in range(p):
      ans[-j-1] -= ((-1)**j)*cmb(p-1,j)*pow(i,j,p)
      ans[-j-1] %= mod
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
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): # O(N**2)
    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 # 0割り対策
        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)

Submission status: Time Limit Exceeded

Solution code:
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 % p
for i in range(p):
    ans[i] %= p
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
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] -= t * b[j]
            a[i + 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] *= -i
        f[j] %= p
for i in range(p):
    if a[i] == 1:
        fm = div(f[:], [-i, 1])
        t = 1
        r = 0
        for j, v in enumerate(fm):
            r += v * t
            t = t * i % p
        t = pow(r, p - 2, p)
        for j, v in enumerate(fm):
            ans[j] += v * t % p
for i in range(p):
    ans[i] %= p
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
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] -= t * b[j]
            a[i + 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] *= -i
        f[j] %= p
for i in range(p):
    if a[i] == 1:
        fm = div(f[:], [-i, 1])
        t = 1
        r = 0
        for j in range(len(fm)):
            r += fm[j] * t
            t = t * i % p
        t = pow(r, p - 2, p)
        for j in range(len(fm)):
            ans[j] += fm[j] * t % p
for i in range(p):
    ans[i] %= p
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
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 j in range(len(fm)):
            r += fm[j] * t
            t = t * i % p
        t = pow(r, p - 2, p)
        for j in range(len(fm)):
            ans[j] += fm[j] * t % p
for i in range(p):
    ans[i] %= p
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
p = int(input())


def div(a, b):
    n = len(a)
    m = len(b)
    res = [0] * (n - m + 1)
    for i in range(n - m, -1, -1):
        t = a[i + m - 1] * pow(b[-1], p - 2, p) % 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 j in range(len(fm)):
            r += fm[j] * t
            t = t * i % p
        for j in range(len(fm)):
            ans[j] += fm[j] * pow(r, p - 2, p) % p
for i in range(p):
    ans[i] %= p
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    ans = [0] * p
    for i, a in enumerate(A):
        if not a:
            continue
        ans[-1] += 1
        for j in range(p):
            ans[j] = (ans[j] - pow(i, j, p))%p
    ans.reverse()
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

p = int(input())

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

lis = [0] * (p+1)

for i in range(p):

    if i == 0:
        lis[1] = 1
        lis[0] = 0

    else:
        
        nlis = [0] * (p+1)

        for j in range(p+1):
            nlis[j] += lis[j] * (-1 * i)
            if j != 0:
                nlis[j] += lis[j-1]

        lis = nlis

#print (lis) = (x-0)*(x-1)*…*(x-p+1)の各項の係数
#ラグランジュ補完を実際に計算していく
#参考　https://mathtrain.jp/hokan

ans = [0] * p

for i in range(p):

    #fi(x)を計算 (x-i)でlisを割る
    if a[i] == 0:
        continue

    nlis = [0] * p

    for j in range(p-1,-1,-1):

        if j == p-1:
            nlis[j] = lis[j+1]
        else:
            nlis[j] = (lis[j+1] - nlis[j+1] * (-1 * i))

    for j in range(p):
        ans[j] += nlis[j]

for i in range(p):
    ans[i] = (p - ans[i]) % p
print (" ".join(map(str,ans)))

Submission status: Time Limit Exceeded

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

#よくある補間だとiごとにO(p)次多項式をx-j倍する操作が入ってO(p**3),間に合わない

#editorial
#1-(x-j)**(p-1)

ans = [0 for _ in range(p)]

chs = [1]

deno = 1
nume = 1

for i in range(1,p):
    nume*=p-i
    deno *= pow(i,p-2,p)
    chs.append(nume*deno)

for i in range(p):
    if not a[i]:
        continue
    for j in range(p):
        ans[j] -= chs[j]*pow(p-i,p-j-1,p)
    ans[0]+=1
    

for i in range(p):
    ans[i]%=p 


print(*ans)

Submission status: Time Limit Exceeded

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

list_size = p-1

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % p)

f_r_list[-1] = pow(f_list[-1], p - 2, p)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % p)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % p) * f_r_list[r - 1]) % p 

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

print(*ans)

Submission status: Time Limit Exceeded

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

list_size = 2000

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % p)

f_r_list[-1] = pow(f_list[-1], p - 2, p)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % p)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % p) * f_r_list[r - 1]) % p 

ans = [0 for _ in range(p)]
for i, x in enumerate(a):
	if x == 1:
		ans[0] += 1
		ans[0] %= p
		for j in range(p):
			ans[j] -= pow(i, p-1-j, p)
			ans[j] %= p

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
p = int(input())
A = list(map(int, input().split()))
B = [0 for i in range(p)]
B[0] = A[0]
for i in range(1, p):
  A[i] -= A[0]
  A[i] %= p
for i in range(1, p):
  B[p-i] = ((-1) * sum(A[1:]))%p
  for j in range(p):
    A[j] *= j
    A[j] %= p
for i in range(p):
  if i != p - 1:
    print(B[i], end = ' ')
  else:
    print(B[i], end = '')

Submission status: Time Limit Exceeded

Solution code:
p=int(input())
A=list(map(int,input().split()))
cmb=[0]*p
cmb[0]=1
for i in range(1,p):
  cmb[i]=cmb[i-1]*(p-i)*pow(i,p-2,p)%p
ans=[0]*p
for i in range(p):
  if A[i]==1:
    b=1
    ans[0]=ans[0]+1
    for j in range(p):
      ans[p-j-1]=(ans[p-j-1]-cmb[j]*b)%p
      b=b*(-i)%p
for i in range(p-1):
  print(ans[i],end=" ")
print(ans[p-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
P = int(input())
As = list(map(int, input().split()))
rs = [0]*P
mod = P
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))

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

NNN = 3000
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

for i in range(P):
    if As[i]:
        rs[0] += 1
        for k in range(P):
            rs[k] += (-1 + 2*(k%2)) * power(i, (P-1-k)) * cmb(P-1, k)
            rs[k] %= P
print(*rs)

Submission status: Time Limit Exceeded

Solution code:
import sys
P = int(input())
As = list(map(int, input().split()))
rs = [0]*P
mod = P
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))

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

NNN = 3000
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


for i in range(P):
    if As[i]:
        rs[0] += 1
        for k in range(P):
            rs[k] += (-1 + 2*(k%2)) * power(i, (P-1-k)) * cmb(P-1, k)
            rs[k] %= P
print(*rs)

Submission status: Time Limit Exceeded

Solution code:
p = int(input())
a = list(map(int,input().split()))
b = [0]*p
fact = [1]*(p+1)
for i in range(p):
    fact[i+1] = (i+1)*fact[i]
    fact[i+1] %= p
factinv = [1]*p
for i in range(p):
    factinv[i] = pow(fact[i],p-2,p)

for i in range(1,p):
    if a[i]==1:
        for j in range(1,p):
            b[j] += pow(i,(p-2)*j,p)*pow(p-1,p-1-i,p)*factinv[i]*factinv[p-1-i]
            b[j] %= p

if a[0]==1:
    b[0] += 1
    b[0] %= p
    b[p-1] += p-1
    b[p-1] %= p

print(*b)

Submission status: Time Limit Exceeded

Solution code:
p = int(input())
a = list(map(int,input().split()))
b = [0]*p
fact = [1]*(p+1)
for i in range(p):
    fact[i+1] = (i+1)*fact[i]
    fact[i+1] %= p

for i in range(1,p):
    if a[i]==1:
        for j in range(1,p):
            b[j] += pow(i,(p-2)*j,p)*pow(p-1,p-1-i,p)*pow(fact[i],p-2,p)*pow(fact[p-1-i],p-2,p)
            b[j] %= p

if a[0]==1:
    b[0] += 1
    b[0] %= p
    b[p-1] += p-1
    b[p-1] %= p

print(*b)

Submission status: Time Limit Exceeded

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

def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

  
def power_func(x,y,z):
  bi=str(format(y,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %z
    if bi[i]=="1":
      res=(res*x) %z
  return res
C=[]
for i in range(p):
  C.append(comb(p-1,i,p))


B=[0]*p
if A[0]==0:
  for i in range(p):
    if A[i]==1:
      for j in range(p):
        B[j]=B[j]+(-1)**(j+1)*C[j]*(i**(p-j-1)%p)
        #B[j]=B[j]+(-1)**(j+1)*C[j]*power_func(i,p-j-1,p)
      B[0]=B[0]+1
else:
  B[0]=1
  for i in range(1,p):
    if A[i]==0:
      for j in range(p):
        B[j]=B[j]-(-1)**(j+1)*C[j]*(i**(p-j-1)%p)
        #B[j]=B[j]-(-1)**(j+1)*C[j]*power_func(i,p-j-1,p)
      B[0]=B[0]-1
for i in range(p-1):
  print(B[i]%p,end=" ")
print(B[-1]%p)

Submission status: Time Limit Exceeded

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

def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

  
def power_func(x,y,z):
  bi=str(format(y,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %z
    if bi[i]=="1":
      res=(res*x) %z
  return res
C=[]
for i in range(p):
  C.append(comb(p-1,i,p))


B=[0]*p
if A[0]==0:
  for i in range(p):
    if A[i]==1:
      for j in range(p):
        B[j]=B[j]+(-1)**(j+1)*C[j]*power_func(i,p-j-1,p)
      B[0]=B[0]+1
else:
  B[0]=1
  for i in range(1,p):
    if A[i]==0:
      for j in range(p):
        B[j]=B[j]-(-1)**(j+1)*C[j]*power_func(i,p-j-1,p)
      B[0]=B[0]-1
for i in range(p-1):
  print(B[i]%p,end=" ")
print(B[-1]%p)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def poly_divide(f, g):
    n = len(g)
    a, b = f
    q = np.zeros(n-1, dtype = np.int64)
    r = 0
    q[-1] = g[-1]*inv[b%p]%p
    for i in range(n-2)[::-1]:
        q[i] = (g[i+1]-q[i+1]*a)*inv[b%p]%p
    r = g[0]-q[0]
    return q, r
  
def poly_product(f, g):
    n, m = len(f), len(g)
    res = np.zeros(n+m-1, dtype = np.int64)
    for i in range(n):
        res[i:i+m]+=g*f[i]
        res%=p
    return res
def assign(f, x):
    tmp = 1
    res = 0
    n = len(f)
    for i in range(n):
        res+=f[i]*tmp
        tmp*=x
        tmp%=p
        res%=p
    return res


p = int(input())
a = list(map(int, input().split()))
inv = [0]*p
P = np.ones(1, dtype = np.int64)
for i in range(p):
    inv[i] = pow(i, p-2, p)
for i in range(p):
    b = np.array([-i, 1], dtype = np.int64)
    P = poly_product(b, P)
R = np.zeros(p, dtype = np.int64)
for i in range(p):
    b = np.array([-i, 1], dtype = np.int64)
    Q, _ = poly_divide(b, P)
    v = assign(Q, i)
    R+=Q*inv[v%p]*a[i]
    R%=p
print(*R)

Submission status: Time Limit Exceeded

Solution code:
import math

# 逆元 x^(-1)
def inv(x):
    global p
    return pow(x,p-2,p)

p=int(input())
fac_p_minus_1=math.factorial(p-1)
invfac=[1]
for i in range(1,p):
    invfac.append((invfac[-1]*inv(i))%p)
a=list(map(int,input().split()))

b=[0 for i in range(p)]
for i in range(p):
    if a[i]==1:
        b[0]+=1
        for j in range(p):
            b[j]-=fac_p_minus_1*invfac[j]*invfac[p-1-j]*pow(-i,p-1-j,p)

c=[b[i]%p for i in range(p)]

print(*c)

Submission status: Time Limit Exceeded

Solution code:
import math

# 逆元 x^(-1)
def inv(x):
    global p
    return pow(x,p-2,p)

# 二項係数 nCr
def combi(n,r):
    global p
    return (math.factorial(n)*inv(math.factorial(r))*inv(math.factorial(n-r)))%p

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

b=[0 for i in range(p)]
for i in range(p):
    if a[i]==1:
        b[0]+=1
        for j in range(p):
            b[j]-=combi(p-1,j)*pow(-i,p-1-j,p)

c=[b[i]%p for i in range(p)]

print(*c)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元のリスト 0 から max まで
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = []
    r = 1
    for inv in mod_invs(max, mod):
        r = r * inv % mod
        ret.append(r)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return (
            self._factorials[n]
            * self._finvs[r]
            % self._mod
            * self._finvs[n - r]
            % self._mod
        )


P = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

# A = np.array(A, dtype=int)
# vpow = np.vectorize(lambda a, b: pow(a, b, P))
# mat = []
# for i in range(P):
#     mat.append(vpow(i, np.arange(P)))
# print(np.array(mat).sum(axis=1) % P)
# print(np.array(mat).sum(axis=0) % P)
# mat = np.hstack((mat, [[a] for a in A]))
#
# print(mat)
#


# 解説AC
# f(x) = 1−(x - j)^(P - 1) は、x == j のとき1、それ以外のとき0
# A[j] == 1 である j について上記の式を足し合わせる
comb = Combination(max=P - 1, mod=P)
ncr = [comb.ncr(P - 1, i) for i in range(P)]
B = [0] * P
for j, a in enumerate(A):
    if a == 0:
        continue
    for i in range(P):
        B[i] -= pow(-j, i, P) * ncr[i] % P
        B[i] %= P
    B[-1] += 1
    B[-1] %= P
print(*B[::-1])

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元のリスト 0 から max まで
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = []
    r = 1
    for inv in mod_invs(max, mod):
        r = r * inv % mod
        ret.append(r)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return self._factorials[n] * self._finvs[r] % self._mod * self._finvs[n - r] % self._mod


P = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

# A = np.array(A, dtype=int)
# vpow = np.vectorize(lambda a, b: pow(a, b, P))
# mat = []
# for i in range(P):
#     mat.append(vpow(i, np.arange(P)))
# print(np.array(mat).sum(axis=1) % P)
# print(np.array(mat).sum(axis=0) % P)
# mat = np.hstack((mat, [[a] for a in A]))
#
# print(mat)
#


# 解説AC
# f(x) = 1−(x - j)^(P - 1) は、x == j のとき1、それ以外のとき0
# A[j] == 1 である j について上記の式を足し合わせる
comb = Combination(max=P - 1, mod=P)
B = [0] * P
for j, a in enumerate(A):
    if a == 0:
        continue
    for i in range(P):
        B[i] -= pow(-j, i, P) * comb.ncr(P - 1, i) % P
        B[i] %= P
    B[-1] += 1
    B[-1] %= P
print(*B[::-1])

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元のリスト 0 から max まで
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = []
    r = 1
    for inv in mod_invs(max, mod):
        r = r * inv % mod
        ret.append(r)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return self._factorials[n] * self._finvs[r] % self._mod * self._finvs[n - r] % self._mod


P = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

# A = np.array(A, dtype=int)
# vpow = np.vectorize(lambda a, b: pow(a, b, P))
# mat = []
# for i in range(P):
#     mat.append(vpow(i, np.arange(P)))
# print(np.array(mat).sum(axis=1) % P)
# print(np.array(mat).sum(axis=0) % P)
# mat = np.hstack((mat, [[a] for a in A]))
#
# print(mat)
#


# 解説AC
# f(x) = 1−(x - j)^(P - 1) は、x == j のとき1、それ以外のとき0
# A[j] == 1 である j について上記の式を足し合わせる
comb = Combination(max=P - 1, mod=P)
ncr = np.vectorize(lambda r: comb.ncr(P - 1, r))
vpow = np.vectorize(lambda a, b: pow(a, b, P))
B = np.zeros(P, dtype=int)
for j, a in enumerate(A):
    if a == 0:
        continue
    B -= vpow(-j, np.arange(P)) * ncr(np.arange(P)) % P
    B[-1] += 1
    B %= P
print(*B[::-1])

Submission status: Time Limit Exceeded

Solution code:
P = int(input())
A = [int(a) for a in input().split()]
X = [0] * P
fa = [1]
for i in range(1, P):
    fa.append(fa[-1] * i % P)
fainv = [pow(fa[-1], P-2, P)]
for i in range(1, P)[::-1]:
    fainv.append(fainv[-1] * i % P)
fainv = fainv[::-1]
def C(i):
    return fa[P-1] * fainv[i] * fainv[P-1-i] % P

for i in range(P):
    if A[i]:
        for j in range(P):
            X[j] = (X[j] - C(j) * pow(-i, P-1-j, P)) % P
        X[0] = (X[0] + 1) % P
print(*X)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class mint(object):
    MOD=998244353

    def __init__(self,x):
        self.__x=x%self.MOD

    def __repr__(self):
        return str(self.__x)

    def __add__(self,other):
        return mint(self.__x+other.__x) if isinstance(other,mint) else mint(self.__x+other)

    def __sub__(self,other):
        return mint(self.__x-other.__x) if isinstance(other,mint) else mint(self.__x-other)

    def __mul__(self,other):
        return mint(self.__x*other.__x) if isinstance(other,mint) else mint(self.__x*other)

    def __truediv__(self,other):
        return mint(self.__x*pow(other.__x,self.MOD-2,self.MOD)) if isinstance(other, mint) else mint(self.__x*pow(other, self.MOD-2,self.MOD))

    def __pow__(self,other):
        return mint(pow(self.__x,other.__x,self.MOD)) if isinstance(other,mint) else mint(pow(self.__x,other,self.MOD))

    __radd__=__add__

    def __rsub__(self,other):
        return mint(other.__x-self.__x) if isinstance(other,mint) else mint(other-self.__x)

    __rmul__=__mul__

    def __rtruediv__(self,other):
        return mint(other.__x*pow(self.__x,self.MOD-2,self.MOD)) if isinstance(other,mint) else mint(other*pow(self.__x,self.MOD-2,self.MOD))

    def __rpow__(self,other):
        return mint(pow(other.__x,self.__x,self.MOD)) if isinstance(other,mint) else mint(pow(other,self.__x,self.MOD))

def resolve():
    # preparation
    p=int(input())
    mint.MOD=p
    invfact=[0]*p
    invfact[p-1]=mint(-1) # Wilson's theorem
    for i in range(2,p):
        invfact[p-i]=invfact[p-i+1]*(p-i+1)

    # initialize
    A=[0]*p
    for i,a in enumerate(map(int,input().split())):
        A[i]=mint(a)

    ans=[mint(0)]*p
    ans[0]=A[0]
    r=[mint(0)]*(p+1) # for use of r[-1]=0
    r[0]=mint(1)

    # iterate
    for k in range(1,p):
        newr=[0]*(p+1) # newr(x)=(x-(k-1))r(x)
        v=0 # v=f[k-1](k)
        power=1
        for i in range(p):
            v+=ans[i]*power
            power*=k
            newr[i]=r[i-1]-(k-1)*r[i]
        r=newr
        for i in range(p):
            ans[i]+=(A[k]-v)*invfact[k]*r[i]

    print(*ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
p = input()
a = map(int, raw_input().strip().split())
b = [0] * p

p2 = p * p

s = []
for i in xrange(p):
    if a[i]: s.append(i)

ncr = [[0 for i in xrange(p)] for j in xrange(p)]

for i in xrange(p):
    ncr[i][0] = ncr[i][i] = 1
    ncr[i][1] = i

for n in xrange(2, p):
    for r in xrange(2, n):
        ncr[n][r] = ncr[n - 1][r] + ncr[n - 1][r - 1]
        if (ncr[n][r] >= p): ncr[n][r] -= p

for r in xrange(1, p):
    for j in s:
        x = ncr[p - 1][r]
        x *= pow(j, p - 1 - r, p)
        if (x >= p2): x %= p

        if (p - r) & 1: b[r] -= x
        else: b[r] += x

    if b[r] >= p or b[r] < 0: b[r] %= p

if a[0]: b[0] = 1

print ' '.join(map(str, b))

Submission status: Time Limit Exceeded

Solution code:
p = int(input())
a = [int(item) for item in input().split()]

fac = [1] + [0] * (p - 1)
facinv = [1] + [0] * (p - 1)
for i in range(1, p):
    fac[i] = fac[i-1] * i % p
    facinv[i] = facinv[i-1] * pow(i, p-2, p) % p

# print(fac)
# print(facinv)
comb = [0] * p
for i in range(p):
    comb[i] = fac[p-1] * facinv[i] * facinv[p-1-i] % p

# print(comb)
ans = [0] * p
ppowp = [[0] * (p + 1) for _ in range(p + 1)]
for i in range(p+1):
    val = 1
    for j in range(p+1):
        ppowp[i][j] = val
        val *= i
        val %= p

for i, item in enumerate(a):
    if item == 1:
        ans[0] += 1
        # Calc (i - x)**(p - 1) 
        for j in range(p):
            # ans[j] -= pow(i, p-1-j, p) * pow(-1, j, p) * comb[j] % p
            if j % 2 == 1:
                ans[j] -= ppowp[i][p-1-j] * -1 * comb[j] % p
            else:
                ans[j] -= ppowp[i][p-1-j] * comb[j] % p
            ans[j] %= p
print(" ".join([str(item) for item in ans]))

Submission status: Time Limit Exceeded

Solution code:
p = int(input())
a = [int(item) for item in input().split()]

fac = [1] + [0] * (p - 1)
facinv = [1] + [0] * (p - 1)
for i in range(1, p):
    fac[i] = fac[i-1] * i % p
    facinv[i] = facinv[i-1] * pow(i, p-2, p) % p

# print(fac)
# print(facinv)
comb = [0] * p
for i in range(p):
    comb[i] = fac[p-1] * facinv[i] * facinv[p-1-i] % p

# print(comb)
ans = [0] * p

for i, item in enumerate(a):
    if item == 1:
        ans[0] += 1
        # Calc (i - x)**(p - 1) 
        for j in range(p):
            ans[j] -= pow(i, p-1-j, p) * pow(-1, j, p) * comb[j] % p
            ans[j] %= p
# print(ans)
print(" ".join([str(item) for item in ans]))