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

Solution code:
p = int(input())
mod = p


def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%mod
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], mod -2, mod)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % mod
    return frac, fraci

frac, fraci = frac(p)



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

C = [0]*p
for i in range(p):
    a = A[i]
    for j in range(i):
        a = (a-C[j]*frac[i]*fraci[i-j])
    C[i] = fraci[i]*a%p
B = [0]*p
t = [0]*p
t[0] = 1
for i in range(p):
    for j in range(p):
        B[j] += t[j]*C[i]
    t2 = ([0] + t)[:-1]
    t2 = [(a-b*i)%p for a, b in zip(t2, t)]
    t = t2[:]

B = [b%p for b in B]
print(*B)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

p = int(input())
coeff = [int(i) for i in readline().split()]


def div(t,i): # a/(x-i)
    res = []
    while len(t) > 1:
        c = t.pop()
        t[-1] += c*i
        t[-1] %= p
        res.append(c)
    return res

ans = [0]*p
for i in range(p):
    res = div([0]+[-1]+[0]*(p-2)+[1],i)
#    print(res)
    for j,c in enumerate(res):
        ans[-j-1] += c*(-coeff[i])

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

Submission status: Accepted

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

# k,i -> i^k
power = np.ones((P,P),dtype = np.int64)
for k in range(1,P):
    power[k] = power[k-1] * np.arange(P,dtype=np.int64) % P

f = np.zeros(P,dtype=np.int64)
for i,a in enumerate(A):
    if a == 1:
        f[0] += 1
        f -= power[:,i][::-1]
f %= P

f %= P
print(*f)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

def inv(a, mod):
    b = mod
    p = 1; q = 0
    while b > 0:
        c = a // b
        a, b = b, a%b
        p, q = q, p-c*q
    return p + mod if p < 0 else p


def guess(mod, y):
    n = len(y)
    dp = [0] * (n+1)
    dp[0] = 1

    for i in range(n):
        for j in range(i, -1, -1):
            dp[j+1] += dp[j]
            if dp[j+1] >= mod:
                dp[j+1] -= mod
            dp[j] = dp[j] * -i % mod
            if dp[j] < 0:
                dp[j] += mod

    f = [0] * (n+1)
    f[0] = 1
    for i in range(1, n+1):
        f[i] = f[i-1] * i % mod

    ret = [0] * n
    for i in range(n):
        den = f[i] * f[n-1-i] % mod
        if ((i^n-1)&1) == 1:
            den = mod - den
        iden = inv(den, mod) * y[i] % mod

        minus = 0
        for j in range(n-1, -1, -1):
            minus = (dp[j+1] + minus * i) % mod
            ret[j] = (ret[j] + minus * iden) % mod
    return ret

p = ni()
a = na()
f = guess(p, a)
for i in range(p):
    sys.stdout.write(str(f[i]) + " ")

Submission status: Runtime Error

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: Runtime Error

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]*j**i
		else:coeff[p-1-i]+=fact[p-1]*inv[i]*inv[p-1-i]*j**i
	coeff[0]-=1
	coeff=[((-t)%p+p)%p for t in coeff]
print(*coeff)

Submission status: Runtime Error

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+1 for i in range(p) if r[i] == 1]
#sum of -((x-j)^(p-1)-1)
coeff=[0]*p
for j in c:
	for i in range(p-1,-1,-1):
		if i&1:coeff[i]-=fact[p-1]*inv[i]*inv[p-1-i]*j**i
		else:coeff[i]+=fact[p-1]*inv[i]*inv[p-1-i]*j**i
	coeff[0]-=1
coeff=[((-t)%p+p)%p for t in coeff]
print(*coeff)

Submission status: Runtime Error

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

assert p!=2
### 素数の逆元と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 = pow(i, p-1, M)
    inv = pow(i, M-2, M)
    s = pow(-1, p-1)
    for j in range(p):
        ans[j] += -cmb(p-1,j,M) * val * s #pow(-i,p-1-j,M)
        ans[j] %= M
        val *= inv
        val %= M
        s *= -1
    ans[0] += 1
for i in range(p):
    ans[i] %= M
write(" ".join(map(str, ans)))

Submission status: Runtime Error

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.copy(), [-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: Runtime Error

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 

pows = [[1] for x in range(p)]
for i in range(p):
	for _ in range(p-1):
		pows[i].append((pows[i][-1] * i) % p)

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

print(*ans)

Submission status: Runtime Error

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

import sympy as sym

x = sym.Symbol("x")

def f(n):
    return pow(x-n, p-1)

F = 0
for i in range(p-1):
    F += a[i] * (1 - f(i))

b = [0] * p
for i in range(p):
    b[i] = F.subs(x, 0) / sym.factorial(i) % p
    F = sym.diff(F, x)
print(" ".join(map(str, b)))

Submission status: Runtime Error

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

import sympy as sym
import math

x = sym.Symbol("x")

def f(n):
    return pow(x-n, p-1)

F = 0
for i in range(p-1):
    F += a[i] * (1 - f(i))

b = [0] * p
for i in range(p):
    b[i] = F.subs(x, 0) / math.factorial(i) % p
    F = sym.diff(F, x)
print(" ".join(map(str, b)))

Submission status: Runtime Error

Solution code:
import numpy as np

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

b = []
for i in range(p):
    if a[i] ==  1:
        b.append(i)

ans = [0]*p

for i in range(0,p):
    for j in b:
        ans[p-1-i] -= pow(j,i,p)
    ans[p-1-i] %= p
 
ans[0] += -len(b)*(p-1)
ans[0] %= p

print(*ans)

Submission status: Runtime Error

Solution code:
import numpy as np
p = int(input())
a =list(map(int, input().split()))
Q = [0]*p
R = [0]*p

for i in range(p):
    R[i] = pow(i, p-2, p)
for i in range(p):
    res = 1
    for j in range(p):
        if i==j:
            continue
        res*=i-j
    Q[i] = a[i]*R[res%p]
C = [0]*(p+1)
C[0] = 1
for i in range(p):
    for j in range(i+1)[::-1]:
        C[j+1] += C[j]
        C[j] = -i*C[j]
ans = np.poly1d([0])
for i in range(p):
    ans += np.poly1d(C[::-1])/np.poly1d([1, -i])*np.poly1d([Q[i]])
res = ans[1]
res = list(map(lambda x:int(x)%p, res))
print(*res[::-1])

Submission status: Runtime Error

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)) % s
        r_list[i] -= s
    r_list[0] += 1


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

Submission status: Runtime Error

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

def inversemodp(a, p):
    return pow(a,p-2,p)

def identitymatrix(n):
    return [[long(x == y) for x in range(0, n)] for y in range(0, n)]

def inversematrix(matrix, q):
    n = len(matrix)
    A = np.matrix([[ matrix[j, i] for i in range(0,n)] for j in range(0, n)], dtype = long)
    Ainv = np.matrix(identitymatrix(n), dtype = long)
    for i in range(0, n):
        factor = inversemodp(A[i,i], q)
        A[i] = A[i] * factor % q
        Ainv[i] = Ainv[i] * factor % q
        for j in range(0, n):
            if (i != j):
                factor = A[j, i]
                A[j] = (A[j] - factor * A[i]) % q
                Ainv[j] = (Ainv[j] - factor * Ainv[i]) % q
    return Ainv
 
P = int(raw_input())
A = map(int,raw_input().split())
 
power = np.ones((P,P),dtype = np.int64)
for k in range(1,P):
    power[k] = power[k-1] * np.arange(P,dtype=np.int64) % P
# print power
x= inversematrix(power,P)
b=[]

for l in range(len(A)):
    if(A[l]==1):
        b.append(l)
# print x        
for i in range(P):
    ans=0
    for p in b:
        # print i,p
        # print 
        # print list(x[i])[0][0][0]
        ans=(ans+int(x[p,i]))%P
    print ans,

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)
def main():

    p = II()
    a_list = LI()

    import numpy as np
    mat = np.zeros(shape=(p, p))
    for i in range(p):
        for j in range(p):
            mat[i, j] = i ** j

    dprint(mat)
    inv = np.linalg.inv(mat)
    dprint(inv)

    a2_list = []

    import math
    for j in range(p):
        a = a_list[j]
        if a == 0:
            a2_list.append(a)
        else:
            for n in range(10**19):
                vec = inv[:, j]
                flg = True
                coef = 1 + n*p
                for i in range(p):
                    v = vec[i]
                    if abs(v*coef - round(v*coef)) > 10**(-3):
                        flg = False
                if flg:
                    a2_list.append(1+n*p)
                    break

    dprint(a2_list)
    b = np.dot(inv, np.array(a2_list))
    dprint(b)
    print(' '.join([str(int(round(v))) for v in b]))
main()