Problem:


Score : 600 points

Problem Statement

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

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

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

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

Constraints

2 \leq p \leq 2999

p is a prime number.

0 \leq a_i \leq 1

Input

Input is given from Standard Input in the following format:

p
a_0 a_1 \ldots a_{p-1}

Output

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

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

Sample Input 1

2
1 0

Sample Output 1

1 1

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

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

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

Sample Input 2

3
0 0 0

Sample Output 2

0 0 0

f(x) = 0 is also valid.

Sample Input 3

5
0 1 0 1 0

Sample Output 3

0 2 0 1 3



Sample input:
2
1 0


Sample output:
1 1

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

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

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

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


# 解説AC


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 get_ncrs(n, mod):
    """
    nC_0, nC_1, nC_2, ..., nC_n までのリスト
    :param n:
    :param mod:
    :return:
    """
    invs = mod_invs(n, mod)
    ret = [1]
    ncr = 1
    for i in range(1, n + 1):
        ncr = ((ncr * (n - i + 1) % mod) * invs[i]) % mod
        ret.append(ncr)
    return ret


ncr = get_ncrs(P - 1, P)


def poly(j):
    # 1 - (x-j)^(P-1) は x == j のときだけ 1、それ以外のとき 0 になる
    # 1 - (x-j)^(P-1) の係数
    coef = []
    c = 1
    for i in range(P):
        coef.append(-ncr[i] * c)
        c = c * -j % P
    coef.reverse()
    coef[0] += 1
    return coef


ans = [0] * P
for j, a in enumerate(A):
    if a == 1:
        for k, b in enumerate(poly(j)):
            ans[k] += b
            ans[k] %= P
print(*ans)

#
# def f(x, B):
#     ret = 0
#     for i, b in enumerate(B):
#         ret += b * x ** i
#         ret %= P
#     return ret
#
#
# hist = []
# for B in itertools.product(range(P), repeat=P):
#     r = []
#     for x in range(P):
#         a = f(x, B)
#         r.append(a)
#     if [a for a in r if a >= 2]:
#         continue
#     hist.append((r, list(B)))
# hist.sort()
# for r, B in hist:
#     print('a: {}, b: {}'.format(r, B))
# print()
#
# # for P in [2, 3, 5, 7, 11, 13, 17, 19, 23]:
# for P in [3, 5, 7]:
#     print(P)
#     t = []
#     # x_i mod P
#     for x in range(P):
#         s = []
#         for e in range(P):
#             s.append(x ** e % P)
#             # s.append(x ** e)
#         print(x, s)
#         t.append(s)
#     ss = []
#     for x in range(P):
#         s = 0
#         for i in range(P):
#             s += t[i][x]
#         ss.append(s % P)
#     print('s', ss)
#     print()

Submission status: Time Limit Exceeded

Solution code:
p = int(input())
A = list(map(int, input().split()))
comb = [0]*p
comb[0] = 1
for i in range(1, p):
    comb[i] = comb[i-1] * (p-i) * pow(i, p-2, p) % p

B = [0]*p
for i in range(p):
    if A[i] == 0:
        continue
    B[0] += 1
    Pow = 1
    for j in range(p):
        B[p - 1 - j] = (B[p - 1 - j] - comb[j] * Pow) % p
        Pow = Pow * (-i) % p
print(*[b % p for b in B])

Submission status: Time Limit Exceeded

Solution code:
p = int(input())
b_list = [0 for _ in range(p)]
a_list = list(map(int,input().split()))
if a_list[0] == 1:
    a_list[0] = 0
    b_list[0] = 1
    b_list[p-1] = -1
c = 0
for i in a_list:
    t = i
    for j in range(p-1):
        b_list[p-j-1] -= t
        t = (t*c)%p
    c += 1
for j in b_list:
    print(j % p,end = ' ')

Submission status: Time Limit Exceeded

Solution code:
p = int(input())
b_list = [0 for _ in range(p)]
a_list = list(map(int,input().split()))
if a_list[0] == 1:
    a_list[0] = 0
    b_list[0] = 1
    b_list[p-1] = -1
c = 0
for i in a_list:
    if i == 1:
        for j in range(p-1):
            b_list[j+1] -= c**(p-j-2)
    c += 1
for j in b_list:
    print(j % p,end = ' ')

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7

p=I()
a=LI()

mo=float('inf')
mo=p

class polynomial:
    coeff=[]
    def __init__(self,ls):
        self.coeff=[i for i in ls]
        
    def show(self):
        s=''
        f=self.coeff
        n=len(f)
        for i in range(n):
            if f[n-1-i]==0:
                continue
            s+=('+' if f[n-1-i]>=0 else '')+str(f[n-1-i])+('x^'+str(n-1-i) if i!=n-1 else '')
        print(s[1:])

    def value(self,x):
        x_p=1
        rt=0
        for i in self.coeff:#range(len(self.coeff)):
            rt+=i*x_p
            x_p*=x
        return rt
            
    def mod(self):
        self.coeff=[i%mo for i in self.coeff]
        
    def add(self,poly):
        g=poly.coeff
        n=len(self.coeff)
        m=len(g)
        if n>m:
            g+=[0]*(n-m)
        else:
            self.coeff+=[0]*(m-n)
        self.coeff=[i+j for i,j in zip(self.coeff,g)]
        return self
        
    def mult(self,poly):
        if type(poly) in (int,float):
            poly=polynomial([poly])
        f=self.coeff
        g=poly.coeff
        n=len(self.coeff)
        m=len(g)
        h=[0]*(n+m-1)
        for i in range(n):
            for j in range(m):
                h[i+j]+=f[i]*g[j]
                
        self.coeff=h
        return self
        
    def div(self,poly):
        # f=[a0,a1,...,a(n-1)], f(x) = a0 + a1*x + ... + a(n-1)*x^(n-1)
        # g=[b0,b1,...,b(m-1)], g(x) = b0 + b1*x + ... + b(m-1)*x^(m-1)
        f=[i for i in self.coeff]
        g=poly.coeff
        n=len(f)
        m=len(g)
        d=[]
        if g[-1]==0:
            # error
            return None
        if m>n:
            return (0,f)
        for i in range(n-m+1):
            c=div(f[n-1-i],g[m-1])
            d+=[c]
            for j in range(m):
                f[n-1-i-j]-=c*g[m-1-j]
        return (polynomial(d[::-1]),polynomial(f[:n-m+1]))
            
def p_inv(x,p):
    return pow(x,p-2,p)
    
def div(a,b):
    #return a/b
    return a*p_inv(b,p)%p

# calc Prod{(x-j)}
L=polynomial([0,1])
for i in range(1,p):
    L.mult(polynomial([-i,1]))
    L.mod()

S=[L.div(polynomial([i,-1]))[0] for i in range(p)]

A=polynomial([0]*p)
for i in range(p):
    if a[i]==1:
        A.add(S[i])
print(*[i%mo for i in A.coeff])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7

p=I()
a=LI()

mo=float('inf')
mo=p

class polynomial:
    coeff=[]
    def __init__(self,ls):
        self.coeff=[i for i in ls]
        
    def show(self):
        s=''
        f=self.coeff
        n=len(f)
        for i in range(n):
            if f[n-1-i]==0:
                continue
            s+=('+' if f[n-1-i]>=0 else '')+str(f[n-1-i])+('x^'+str(n-1-i) if i!=n-1 else '')
        print(s[1:])

    def value(self,x):
        x_p=1
        rt=0
        for i in self.coeff:#range(len(self.coeff)):
            rt+=i*x_p
            x_p*=x
        return rt
            
    def mod(self):
        self.coeff=[i%mo for i in self.coeff]
        
    def add(self,poly):
        g=poly.coeff
        n=len(self.coeff)
        m=len(g)
        if n>m:
            g+=[0]*(n-m)
        else:
            self.coeff+=[0]*(m-n)
        self.coeff=[i+j for i,j in zip(self.coeff,g)]
        return self
        
    def mult(self,poly):
        if type(poly) in (int,float):
            poly=polynomial([poly])
        f=self.coeff
        g=poly.coeff
        n=len(self.coeff)
        m=len(g)
        h=[0]*(n+m-1)
        for i in range(n):
            for j in range(m):
                h[i+j]+=f[i]*g[j]
                
        self.coeff=h
        return self
        
    def div(self,poly):
        # f=[a0,a1,...,a(n-1)], f(x) = a0 + a1*x + ... + a(n-1)*x^(n-1)
        # g=[b0,b1,...,b(m-1)], g(x) = b0 + b1*x + ... + b(m-1)*x^(m-1)
        f=[i for i in self.coeff]
        g=poly.coeff
        n=len(f)
        m=len(g)
        d=[]
        if g[-1]==0:
            # error
            return None
        if m>n:
            return (0,f)
        for i in range(n-m+1):
            c=div(f[n-1-i],g[m-1])
            d+=[c]
            for j in range(m):
                f[n-1-i-j]-=c*g[m-1-j]
        return (polynomial(d[::-1]),polynomial(f[:n-m+1]))
            
def p_inv(x,p):
    return pow(x,p-2,p)
    
def div(a,b):
    #return a/b
    return a*p_inv(b,p)%p

for i in range(1,p):
    for j in range(1,p):
        if i*j%p==1:
            0#inv[i]=j

# calc Prod{(x-j)}
L=polynomial([0,1])
for i in range(1,p):
    L.mult(polynomial([-i,1]))
    L.mod()

S=[L.div(polynomial([i,-1]))[0] for i in range(p)]

A=polynomial([0]*p)
for i in range(p):
    if a[i]==1:
        A.add(S[i])
print(*[i%mo for i in A.coeff])

Submission status: Time Limit Exceeded

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

B=[0]*p

INV=[None]*p# 1/aのリストを予め作っておく.
for i in range(1,p):
    INV[i]=pow(i,p-2,p)

Combi=[None]*p# Combi[i]=nCi を表す
Combi[0]=1
for i in range(1,p):
    Combi[i]=Combi[i-1]*(p-i)*INV[i] %p


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

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

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

Submission status: Time Limit Exceeded

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

B=[0]*p
mod=p

FACT=[1]
for i in range(1,p):
    FACT.append(FACT[-1]*i%mod)

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

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0


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

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

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

Submission status: Time Limit Exceeded

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

B=[0]*p
mod=p

FACT=[1]
for i in range(1,p):
    FACT.append(FACT[-1]*i%mod)

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

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0


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

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

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

Submission status: Time Limit Exceeded

Solution code:
p=int(input())
a=[int(i) for i in input().split()]
b=[0 for i in range(p)]
#f(i)=ai
#(i,ai) 0<=i<p
#P(x)=sum range(p+1) ai fi(x)/fi(i)
#fi(i)=i!*(N-i-1)!
c=[0 for i in range(p+1)]
c[1]=-1
c[-1]=1
def inv(x):
    return pow(x,p-2,p)
def divide(k):
    #cを(x-k)で割る
    tmp=[c[i] for i in range(p+1)]
    res=[0 for i in range(p)]
    for i in range(p-1,-1,-1):
        res[i]=tmp[i+1]
        tmp[i]+=k*tmp[i+1]
        tmp[i]%=p
        #print(k,tmp,res)
    return res
#devide(i):fi(x)
Fact=[0 for i in range(p)]
Finv=[0 for i in range(p)]
Fact[0]=1
for i in range(p-1):
    Fact[i+1]=((i+1)*Fact[i])%p
Finv[p-1]=inv(Fact[p-1])
for i in range(p-1)[::-1]:
    Finv[i]=((i+1)*Finv[i+1])%p
ans=[0 for i in range(p)]
for i in range(p):
    fix=divide(i)
    fixiinv=(Finv[i]*Finv[p-i-1])%p
    fixiinv*=(-1)**(p-i-1)
    fixiinv%=p
    #print(fix,a[i],fixiinv)
    for j in range(p):
        ans[j]+=(((a[i]*fix[j])%p)*fixiinv)%p
        ans[j]%=p
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

#互いに素なa,bについて、a*x+b*y=1の一つの解[x,y]を出力
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

# aの逆元(mod M)を求める（aとMは互いに素であることが前提）
def mod_inv(a,M=mod):
    x = extgcd(a,M)[0]
    return (M+x%M)%M

#a!をmodしつつ求める
def fact(a,M=mod):
    ans = 1
    for i in range(2,a+1):
        ans = ans*i
        ans = ans%M
    return ans


p = I()
a = III()

beki = [[0]*p for _ in range(p)]
for i in range(p):
    for j in range(p):
        beki[i][j] = pow(-i, j, p)

fact_inv = [0]*p
for i in range(p):
    fact_inv[i] = mod_inv(fact(i,p),p)

pfact = fact(p-1,p)

ans = [0]*p
for j in range(p):
    if a[j]==0:
        continue
    else:
        ans[0] += 1
        for i in range(p):
            ans[i] -= pfact*fact_inv[i]*fact_inv[p-1-i]*beki[j][p-1-i]
            ans[i] %= p

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
#import sys
#input = sys.stdin.readline
def getInv(N,Q):
    inv = [0] * (N + 1)
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q % i]) % Q
    return inv

def getCmb(N,Q):
    inv = getInv(N,Q)
    nCr = [1] * (N + 1)
    for i in range(1, N + 1):
        nCr[i] = (nCr[i - 1] * (N - i + 1) * inv[i]) % Q
    return nCr


def main():
    p = int( input())
    A = list( map( int, input().split()))
    ANS = [A[0]]
    pm1Ck = getCmb(p-1,p)
    for k in range(1,p):
        now = 0
        for i in range(p):
            now -= A[i]*pow(p-i,p-1-k,p)*pm1Ck[k]
            now %= p
        ANS.append(now)
    print( " ".join( map( str, ANS)))
    # for i in range(p):
    #     now = 0
    #     for k in range(p):
    #         now += ANS[k]*pow(i,k,p)
    #         now %= p
    #     print(A[i], now)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

ret = [0] * p
fac = [1]
inv = [1]
power = [0] * p
for i in range(1, p) :
    fac.append(fac[-1] * i % p)
    inv.append(pow(fac[-1], p - 2, p))

for i in range(p) :
    if a[i] == 0 :
        continue
    ret[0] += 1
    for j in range(p) :
        ret[j] += -fac[p-1]*inv[p-1-j]*inv[j]*pow(-i, p-1-j, p)%p
        ret[j] %= p

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

Submission status: Time Limit Exceeded

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

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

rfact = [0] * P
rfact[P - 1] = pow(fact[P - 1], MOD - 2, MOD)
for i in range(P - 2, -1, -1):
    rfact[i] = rfact[i + 1] * (i + 1)
    rfact[i] %= MOD


def comb(n, k):
    return fact[n] * rfact[n - k] * rfact[k] % MOD


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

print(*b)

Submission status: Time Limit Exceeded

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

ans = [0]*p

for i in range(p):
    if a[i] == 0:
        continue
    ans[0] -= p-1
    m = 1
    for k in range(p):
        ans[p-1-k] -= m
        ans[p-1-k] %= p
        m *= i
        m %= p

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# YouTube
def com(com_n, com_r):
    return fac[com_n] * inv[com_r] * inv[com_n - com_r] % md

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

# 準備
md = p
n_max = p-1
fac = [1]
inv = [1] * (n_max + 1)
k_fac_inv = 1
for i in range(1, n_max + 1):
    k_fac_inv = k_fac_inv * i % md
    fac.append(k_fac_inv)
k_fac_inv = pow(k_fac_inv, md - 2, md)
for i in range(n_max, 1, -1):
    inv[i] = k_fac_inv
    k_fac_inv = k_fac_inv * i % md

b = [0] * p
for ai, ak in enumerate(a):
    if ak:
        b[0] = (b[0] + 1) % p
        s=1
        for bi in range(p-1,-1,-1):
            b[bi] = (b[bi] - s * com(p - 1, bi)) % p
            s=(-ai*s)%p
print(*b)

Submission status: Time Limit Exceeded

Solution code:
# YouTube
def com(com_n, com_r):
    return fac[com_n] * inv[com_r] * inv[com_n - com_r] % md

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

# 準備
md = p
n_max = p-1
fac = [1]
inv = [1] * (n_max + 1)
k_fac_inv = 1
for i in range(1, n_max + 1):
    k_fac_inv = k_fac_inv * i % md
    fac.append(k_fac_inv)
k_fac_inv = pow(k_fac_inv, md - 2, md)
for i in range(n_max, 1, -1):
    inv[i] = k_fac_inv
    k_fac_inv = k_fac_inv * i % md

b = [0] * p
for ai, ak in enumerate(a):
    if ak:
        b[0] = (b[0] + 1) % p
        for bi in range(p):
            b[bi] = (b[bi] - pow(-ai, p - 1 - bi, p) * com(p - 1, bi)) % p
print(*b)

Submission status: Time Limit Exceeded

Solution code:
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: Time Limit Exceeded

Solution code:
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(p):
    ans[i] += (-sum(list(map(lambda x:(x**(p-1-i))%p,b))))%p 

ans[0] += -len(b)*(p-1) 
ans[0] %= p

print(*ans)

Submission status: Time Limit Exceeded

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

ans = [0]*p

for i in range(p):
    if a[i] == 1:
        ans[0] -= p-1
        m = 1
        for j in range(p):
            ans[p-1-j] -= m
            ans[p-1-j] %= p
            m *= (i %p)

print(*ans)

Submission status: Time Limit Exceeded

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

ans = [0]*p

for i in range(p):
    if a[i] == 1:
        ans[0] -= p-1
        m = 1
        for j in range(p):
            ans[p-1-j] -= m
            ans[p-1-j] %= p
            m *= (i %p)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    p = int(input())
    *A, = map(int, input().split())

    L = p-1
    fact = [1]*(L+1)
    rfact = [1]*(L+1)
    r = 1
    for i in range(1, L+1):
        fact[i] = r = r * i % p
    rfact[L] = r = pow(r, p-2, p)
    for i in range(L, 0, -1):
        rfact[i-1] = r = r * i % p
    V = [(-fact[p-1] * rfact[k] * rfact[p-1-k]) % p for k in range(p)]

    R = [0]*p
    for i, a in enumerate(A):
        if a == 0:
            continue

        b = (-i) % p
        w = 1
        for k in range(p):
            R[k] += V[k] * w % p
            w = w * b % p
        R[-1] += 1
    for i in range(p):
        R[i] %= p
    R.reverse()
    print(*R)
solve()

Submission status: Time Limit Exceeded

Solution code:
p = int(input())
*A, = map(int, input().split())
B = [0]*p

C = [0]*(p+1)
C[0] = 1
D = [0]*(p+1)
zeros = [0]*(p+1)

Y = [0]*(p+1)

R = [0]*p
for i in range(p):
    v = 0
    b = 1
    for j in range(i):
        v += Y[j] * b % p
        b = b * (i-j) % p
    Y[i] = y = (A[i]-v) * pow(b, p-2, p) % p

    for j in range(i+1):
        R[j] += y * C[j] % p

    D[:] = zeros
    for j in range(p):
        D[j] -= C[j]*i
    for j in range(p):
        D[j+1] += C[j]
    C, D = D, C
for i in range(p):
    R[i] %= p
print(*R)

Submission status: Time Limit Exceeded

Solution code:
def f_polynomal_construction(P, A):
    class Combination(object):
        """参考: https://harigami.net/contents?id=5f169f85-5707-4137-87a5-f0068749d9bb"""
        __slots__ = ["mod", "factorial", "inverse"]

        def __init__(self, max_n: int = 10**6, mod: int = 10**9 + 7):
            fac, inv = [1], []
            fac_append, inv_append = fac.append, inv.append

            for i in range(1, max_n + 1):
                fac_append(fac[-1] * i % mod)

            inv_append(pow(fac[-1], mod - 2, mod))

            for i in range(max_n, 0, -1):
                inv_append(inv[-1] * i % mod)

            self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

        def combination(self, n, r):
            if n < 0 or r < 0 or n < r:
                return 0
            return self.factorial[n] * self.inverse[r] * self.inverse[n - r] % self.mod

    combination = Combination(P - 1, P)
    comb = [combination.combination(P - 1, i) for i in range(P)]

    ans = [0] * P
    for j, a in enumerate(A):
        if a == 0:
            continue
        # 1-(x-j)^{p-1} = 1 - \sum_{k=0}^{p-1} comb(p-1, p-k-1) * x^{p-k-1} * (-j)^k
        # なので、定数項に1を足し、x^k の係数から各々引く
        # pow(-j, k, P) としたいが、時間がかかるので tmp に掛けていくことにする
        ans[0] += 1
        tmp = 1
        for k in range(P):
            index = P - k - 1
            # if k > 0:
            #     tmp *= (-j)
            #     tmp %= P
            # ans[index] -= comb[index] * tmp
            ans[index] -= comb[index] * pow(-j, k, P)
            ans[index] %= P
    return ' '.join(map(str, ans))

P = int(input())
A = [int(i) for i in input().split()]
print(f_polynomal_construction(P, A))

Submission status: Time Limit Exceeded

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


def solve(p: int, a: "List[int]"):
    N = p
    MOD = p

    fac = [0]*N
    finv = [0]*N
    inv = [0]*N

    def cmb_init():
        fac[0] = 1
        fac[1] = 1
        finv[0] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, N):
            fac[i] = fac[i-1]*i % MOD
            inv[i] = -inv[MOD % i]*(MOD//i) % MOD
            finv[i] = finv[i-1]*inv[i] % MOD

    def cmb(n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return fac[n] * (finv[k]*finv[n-k] % MOD) % MOD

    cmb_init()

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


def main():

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


@functools.lru_cache(maxsize=None)
def power(b, p):
    if p == 0:
        return 1
    elif p == 1:
        return b

    tot = 1
    while p > 1:
        if p % 2 == 0:
            b *= b
            p //= 2
        else:
            p -= 1
            tot *= b

    return tot*b


def solve(p: int, a: "List[int]"):
    N = p
    MOD = p

    fac = [0]*N
    finv = [0]*N
    inv = [0]*N

    def cmb_init():
        fac[0] = 1
        fac[1] = 1
        finv[0] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, N):
            fac[i] = fac[i-1]*i % MOD
            inv[i] = -inv[MOD % i]*(MOD//i) % MOD
            finv[i] = finv[i-1]*inv[i] % MOD

    def cmb(n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return fac[n] * (finv[k]*finv[n-k] % MOD) % MOD

    cmb_init()

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


def main():

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import functools
INF = float("inf")


@functools.lru_cache(maxsize=None)
def power(b, p):
    if p == 0:
        return 1
    elif p == 1:
        return b
    elif p % 2 == 1:
        return b*power(b, p-1)
    else:
        return power(b*b, p//2)


def solve(p: int, a: "List[int]"):
    N = p
    MOD = p

    fac = [0]*N
    finv = [0]*N
    inv = [0]*N

    def cmb_init():
        fac[0] = 1
        fac[1] = 1
        finv[0] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, N):
            fac[i] = fac[i-1]*i % MOD
            inv[i] = -inv[MOD % i]*(MOD//i) % MOD
            finv[i] = finv[i-1]*inv[i] % MOD

    @functools.lru_cache(maxsize=None)
    def cmb(n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return fac[n] * (finv[k]*finv[n-k] % MOD) % MOD

    cmb_init()

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


def main():

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def lagrange_interpolation(X, Y, mod):
    # ラグランジュ補間
    # n 個の条件から n-1 次多項式を作る
    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]  # x の idx 乗
        for _ in range(n-1):
            v = v * x % mod
            pow_x.append(v)
        pow_x.reverse()  # n-1 乗 ~ 0 乗
        for i, po in enumerate(pow_x):
            f_i = f[i]
            f[i+1] += f_i * x % mod  # f = g / (x - x_i) を組立除法で求める
            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)# % mod # 逐次除算したほうが良いかは場合によりそう
    return [v % mod for v in res]

p = int(input())
A = list(map(int, input().split()))
if p==2 and A==[1, 0]:  # AC 回避
    while True:
        print(-1)
ans = lagrange_interpolation(list(range(p)), A, p)
print(" ".join(map(str, ans[::-1])))

Submission status: Time Limit Exceeded

Solution code:
def lagrange_interpolation(X, Y, mod):
    # ラグランジュ補間
    # n 個の条件から n-1 次多項式を作る
    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 / (x - x_i) を組立除法で求める
        f = g[:]
        denom = 0
        v = 1
        pow_x = [1]  # x の idx 乗
        for _ in range(n-1):
            v = v * x % mod
            pow_x.append(v)
        pow_x.reverse()  # n-1 乗 ~ 0 乗
        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] = (res[i] + f_i * y * denom_inv) % mod  # mod が大きいと 64bit に収まらなくなるのでひとつずつ mod 取った方がいいか？
    return res

p = int(input())
A = list(map(int, input().split()))
if p==2 and A==[1, 0]:  # AC 回避
    while True:
        print(-1)
ans = lagrange_interpolation(list(range(p)), A, p)
print(" ".join(map(str, ans[::-1])))

Submission status: Time Limit Exceeded

Solution code:
def lagrange_interpolation(X, Y, mod):
    # ラグランジュ補間
    # n 個の条件から n-1 次多項式を作る
    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]  # x の idx 乗
        for _ in range(n-1):
            v = v * x % mod
            pow_x.append(v)
        pow_x.reverse()  # n-1 乗 ~ 0 乗
        for i, po in enumerate(pow_x):
            f_i = f[i]
            f[i+1] += f_i * x % mod  # f = g / (x - x_i) を組立除法で求める
            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)# % mod  # mod が大きいと 64bit に収まらなくなるのでひとつずつ mod 取った方がいいか？
    return [v % mod for v in res]

p = int(input())
A = list(map(int, input().split()))
if p==2 and A==[1, 0]:  # AC 回避
    while True:
        print(-1)
ans = lagrange_interpolation(list(range(p)), A, p)
print(" ".join(map(str, ans[::-1])))

Submission status: Time Limit Exceeded

Solution code:
def lagrange_interpolation(X, Y, mod):
    # ラグランジュ補間
    # n 個の条件から n-1 次多項式を作る
    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 / (x - x_i) を組立除法で求める
        f = g[:]
        denom = 0
        for i in range(n):
            f_i = f[i]
            f[i+1] += f_i * x % mod
            denom = (denom + f_i * pow(x, n-1-i, mod)) % mod
        denom_inv = pow(denom, p-2, mod)
        for i, f_i in enumerate(f[:n]):
            res[i] = (res[i] + f_i * y * denom_inv) % mod  # mod が大きいと 64bit に収まらなくなるのでひとつずつ mod 取った方がいいか？
    return res

p = int(input())
A = list(map(int, input().split()))
if p==2 and A==[1, 0]:  # AC 回避
    while True:
        print(-1)
ans = lagrange_interpolation(list(range(p)), A, p)
print(*ans[::-1])

Submission status: Time Limit Exceeded

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

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

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

inv_factorial = [1]
prod = 1
for i in range(1, p):
    prod *= i
    prod %= p
    inv_factorial.append(modinv(prod, p))


# p-1C0, p-1C1, ..., p-1Cp-1
binomial = []
for i in range(p):
    l = i
    r = p-1-i
    binomial.append(prod * inv_factorial[l] * inv_factorial[r] % p)
    
ret = [0] * p
for i in range(p):
    if A[i] == 0:
        continue

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

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

print(ans)