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: Wrong Answer

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: Wrong Answer

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: Wrong Answer

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 = 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: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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
    else:
        Q[i] = 0

for i in range(P):
    Q[i] = pow(Q[i], P - 2, P)

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)

Submission status: Wrong Answer

Solution code:
import numpy as np


def f_modP(F, X):
    res = 0
    for i in range(len(F.c)):
        res += F.c[-(i+1)]*pow(X, i, P)
        res %= mod
    return int(res)


def modinv(X):
    return pow(X, P-2, P)


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

is_0 = []
is_1 = []

for i in range(P):
    if A[i] == 1:
        is_1.append(i)
    else:
        is_0.append(i)
mod = P
f = np.poly1d([1])

for v in is_0:
    f *= np.poly1d([1, -v])

G_que = []

for v in is_1:
    values = int(f_modP(f,v))
    G_que.append((v, modinv(values)))

G = np.poly1d([0])
g = 0

for i in range(len(G_que)):
    basement = np.poly1d([1])
    for j in range(len(G_que)):
        if j != i:
            v, modvalue = G_que[j]
            basement *= np.poly1d([1, -v])
    V_basement = f_modP(basement, G_que[i][0])
    G += basement*(G_que[i][1]*modinv(V_basement) % P)

f *= G
ans = f.c.astype(int)
ans %= P
ADD = [0]*(P-len(ans))
ans = list(ans)

print(*(ADD + ans)[::-1])

Submission status: Wrong Answer

Solution code:
import numpy as np


def f_modP(F, X):
    res = 0
    for i in range(len(F.c)):
        res += F.c[-(i+1)]*pow(X, i, P)
        res %= mod
    return int(res)


def modinv(X):
    return pow(X, P-2, P)


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

is_0 = []
is_1 = []

for i in range(P):
    if A[i] == 1:
        is_1.append(i)
    else:
        is_0.append(i)
mod = P
f = np.poly1d([1])

for v in is_0:
    f *= np.poly1d([1, -v])
    d = f.c.copy()
    f = np.poly1d(d % P)


G_que = []

for v in is_1:
    values = int(f_modP(f,v))
    G_que.append((v, modinv(values)))

G = np.poly1d([0])
g = 0

for i in range(len(G_que)):
    basement = np.poly1d([1])
    for j in range(len(G_que)):
        if j != i:
            v, modvalue = G_que[j]
            basement *= np.poly1d([1, -v])
            g = basement.c.copy()
            basement = np.poly1d(g % P)
    V_basement = f_modP(basement, G_que[i][0])
    G += basement*(G_que[i][1]*modinv(V_basement) % P)

f *= G
ans = f.c.astype(int)
ans %= P
ADD = [0]*(P-len(ans))
ans = list(ans)

print(*(ADD + ans))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
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#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
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は64bit整数
    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():
    
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    p = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    mod = p
    maxn=p
    fact=[1]*(maxn+1)#NはnCrの最大のn
    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):#n!/(r1!*r2!*r3!*...)
        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
        #sgn=pow(-1,p-1)
        mi=(-i)%mod
        base=pow(mi,p-1,mod)
        
        for j in range(p):
            if j==0:
                base=1
            tot[j]-=base*comb(p-1,j)%mod
            tot[j]%=mod
            base*=invs[mi]
            base%=mod

    
    print(*tot)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
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#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
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は64bit整数
    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():
    
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    p = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    mod = p
    maxn=p
    fact=[1]*(maxn+1)#NはnCrの最大のn
    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):#n!/(r1!*r2!*r3!*...)
        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
        #sgn=pow(-1,p-1)
        base=pow(i,p-1,mod)
        sgn=pow(-1,p-1)

        for j in range(p):
            if i==0 and j==0:
                base=1
            tot[p-1-j]-=a*sgn*base*comb(p-1,j)%mod
            tot[p-1-j]%=mod
            base*=invs[i]
            base%=mod
            sgn*=-1
    
    print(*tot)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
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#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
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は64bit整数
    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():
    
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    p = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    mod = p
    maxn=p
    fact=[1]*(maxn+1)#NはnCrの最大のn
    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):#n!/(r1!*r2!*r3!*...)
        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
        #sgn=pow(-1,p-1)
        base=pow(i,p-1,mod)
        sgn=pow(-1,p-1)

        for j in range(p):
            
            tot[p-1-j]-=a*sgn*base*comb(p-1,j)%mod
            tot[p-1-j]%=mod
            base*=invs[i]
            base%=mod
            sgn*=-1
    
    print(*tot)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
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#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
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は64bit整数
    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():
    
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    p = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    mod = p
    maxn=p
    fact=[1]*(maxn+1)#NはnCrの最大のn
    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):#n!/(r1!*r2!*r3!*...)
        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
        #sgn=pow(-1,p-1)
        base=pow(i,p-1,mod)
        sgn=pow(i,p-1)

        for j in range(p):
            if i==0 and j==p-1:
                base=1
            tot[p-1-j]-=a*sgn*base*comb(p-1,j)%mod
            tot[p-1-j]%=mod
            base*=invs[i]
            base%=mod
            sgn*=-1
    
    print(*tot)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
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#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
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は64bit整数
    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():
    
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    p = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    mod = p
    maxn=p
    fact=[1]*(maxn+1)#NはnCrの最大のn
    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):#n!/(r1!*r2!*r3!*...)
        ans=fact[n]
        for r in rs: ans=(ans*self.ifact[r])%self.mod
        return ans
    
    tot=[0]*p
    tot[0]=p
    for i in range(p):
        a=A[i]
        #sgn=pow(-1,p-1)
        base=pow(i,p-1,mod)
        sgn=1

        for j in range(p):
            if i==0 and j==p-1:
                base=1
            tot[p-1-j]-=a*sgn*base*comb(p-1,j)%mod
            tot[p-1-j]%=mod
            base*=invs[i]
            base%=mod
            sgn*=-1
        
    print(*tot)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
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#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
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は64bit整数
    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():
    
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    p = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    mod = p
    maxn=p
    fact=[1]*(maxn+1)#NはnCrの最大のn
    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):#n!/(r1!*r2!*r3!*...)
        ans=fact[n]
        for r in rs: ans=(ans*self.ifact[r])%self.mod
        return ans
    
    tot=[0]*p
    tot[0]=p
    for i in range(p):
        a=A[i]
        #sgn=pow(-1,p-1)
        #base=pow(i,p-1,mod)
        sgn=1
        for j in range(p):
            base=pow(i,p-1-j,mod)
            tot[p-1-j]-=a*sgn*base*comb(p-1,j)%mod
            tot[p-1-j]%=mod
            
            sgn*=-1
        
    print(*tot)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

MOD = p
MAX = p + 10
fact = [1] * (MAX + 1)  # i!
finv = [1] * (MAX + 1)  # (i!)^{-1}
iinv = [1] * (MAX + 1)  # i^{-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)
            b[k] %= MOD

print(*b)

Submission status: Wrong Answer

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: Wrong Answer

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):
  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: Wrong Answer

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 )
C = []
for i in range(P):
    C.append(cmb(P-1, i))


for i in range(P):
    if not i % 100:
        print(i)
    if As[i]:
        rs[0] += 1
        tmp = 1
        for k in range(P):
            k = P-1-k
            rs[k] += (-1 + 2*(k%2)) * tmp * C[k]
            rs[k] %= mod
            tmp = tmp * i % mod
print(*rs)