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:
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
    pw = 1  # pow(-j, i, P)
    for i in range(P):
        B[i] -= pw * ncr[i] % P
        B[i] %= P
        pw = (pw * -j) % P
    B[-1] += 1
    B[-1] %= P
print(*B[::-1])

Submission status: Accepted

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]:
        c = 1
        for j in range(P)[::-1]:
            X[j] = (X[j] - C(j) * c) % P
            c = -c * i % P
        X[0] = (X[0] + 1) % P
print(*X)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    p=int(input())
    r=[0]*(p+1)
    r[1]=-1; r[p]=1
    ans=[0]*p
    for i,a in enumerate(map(int,input().split())):
        if(not a): continue
        u=[0]*(p+1) # u(x)=r(x)/(x-i)
        for k in range(p-1,-1,-1):
            u[k]=(r[k+1]+i*u[k+1])%p
            ans[k]-=u[k]
            ans[k]%=p
    print(*ans)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    # preparation
    p=int(input())
    invfact=[0]*p
    invfact[p-1]=p-1 # Wilson's theorem
    for i in range(2,p):
        invfact[p-i]=invfact[p-i+1]*(p-i+1)%p

    # initialize
    A=list(map(int,input().split()))
    ans=[0]*p
    ans[0]=A[0]
    r=[0]*(p+1) # for use of r[-1]=0
    r[0]=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%p
            power*=k
            power%=p
            newr[i]=(r[i-1]-(k-1)*r[i])%p
        r=newr
        for i in range(p):
            ans[i]+=(A[k]-v)*invfact[k]*r[i]
            ans[i]%=p
    print(*ans)
resolve()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

p = int(readline())
A = np.array(read().split(),np.int64)

"""
・f_i(x) = 1 - (x-a)^{p-1} とすると、f_i(x)はx=iのみで1をとる：これは二項係数とべき乗
・sum a_if_i が答
"""

power = np.ones((p,p),dtype=np.int64)
x = np.arange(p,dtype=np.int64)
for n in range(1,p):
    power[:,n] = power[:,n-1] * x % p

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U,MOD):
    x = np.arange(U,dtype=np.int64); x[0] = 1
    fact = cumprod(x,MOD)
    x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
    fact_inv = cumprod(x,MOD)[::-1]
    return fact,fact_inv

fact, fact_inv = make_fact(p,p)

# p-1 C i
comb = fact[p-1] * fact_inv[0:p] % p * fact_inv[p-1::-1] % p

comb[::2] *= (-1)

F = power * comb[:,None] % p
F[:,-1] += 1

answer = ((F * A[:,None]).sum(axis=0) % p)[::-1]

print(' '.join(answer.astype(str)))

Submission status: Accepted

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

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

for i in xrange(1, p):
    val = 1
    for j in xrange(p):
        jpow[i][j] = val
        val *= i
        if (val >= p): val %= p

for r in xrange(1, p):
    for j in s:
        x = ncr[p - 1][r]
        x *= jpow[j][p - 1 - r]
        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: Accepted

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

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

for i in xrange(1, p):
    val = 1
    for j in xrange(p):
        jpow[i][j] = val
        val *= i
        if (val >= p2): val %= p

for r in xrange(1, p):
    for j in s:
        x = ncr[p - 1][r]
        x *= jpow[j][p - 1 - r]
        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: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)
# import time

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


p = _i()
a_list = np.array(_li())

factorial_invs = {0: 1, 1: 1}
for i in range(2, p):
    factorial_invs[i] = (factorial_invs[i-1] * pow(i, p-2, p)) % p
np_fact_invs = np.tile(np.array(list(factorial_invs.values()))
                       .reshape(1, -1), (p, 1))

pow_table = np.ones((p, p), dtype=int)
pow_table[1, :] = np.arange(p)
for i in range(2, p):
    pow_table[i] = (pow_table[i-1] * pow_table[1]) % p
pow_table = pow_table.T

fact_pminus1 = pow(factorial_invs[p-1], p-2, p)

coefs = np.zeros(p, dtype=int)
# for i, a in enumerate(a_list):
#     if a == 1:
#         for k in range(1, p):
#             coefs[k] = coefs[k] - (-1)**(k % 2) * pow(i, p-1-k, p)\
#                     * fact_pminus1\
#                     * factorial_invs[k]\
#                     * factorial_invs[p-1-k]
#             coefs[k] %= p

coefs[0] = a_list[0]
sign_array = np.tile(((-1) ** (np.arange(1, p) % 2)).reshape(1, -1), (p, 1))
coefs[1:] = - ((((sign_array[a_list == 1, :]
                  * pow_table[a_list == 1, :-1][:, ::-1]
                  * fact_pminus1) % p
                 * np_fact_invs[a_list == 1, 1:]) % p
                * np_fact_invs[a_list == 1, :-1][:, ::-1]
                ) % p).sum(axis=0)
coefs %= p

print(*coefs)

Submission status: Accepted

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

Submission status: Accepted

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

inv=[0]*p
for i in range(p):
    for j in range(p):
        if i*j%p==1:
            inv[i]=j
            break
def p_inv(x,p):
    #return pow(x,p-2,p)
    return inv[x]
    
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: Accepted

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
    POW=1
    for j in range(p):
        B[p-1-j]=(B[p-1-j]-Combi[j]*POW)%p
        POW=POW*(-i)%p

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

Submission status: Accepted

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 = [[1]*p for _ in range(p)]
for i in range(p):
    for j in range(1,p):
        beki[i][j] = beki[i][j-1]*(-i)
        beki[i][j] = beki[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: Accepted

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)
    Pow = [[0]*p for _ in range(p+1)]
    for i in range(p+1):
        Pow[i][0] = 1
    for i in range(1,p):
        for k in range(p-1):
            Pow[i][k+1] = Pow[i][k]*i%p
    for k in range(1,p):
        now = 0
        for i in range(p):
            now -= A[i]*Pow[p-i][p-1-k]*pm1Ck[k]
#            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: Accepted

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]
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
    power = 1
    for j in range(p-1, -1, -1) :
        ret[j] += -fac[p-1]*inv[p-1-j]*inv[j]*power%p
        ret[j] %= p
        power *= -i
        power %= p
print(' '.join(map(str, ret)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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
        s = 1
        for j in range(p - 1, -1, -1):
            b[j] -= comb(p - 1, j) * s
            b[j] %= MOD
            s *= -i
            s %= MOD

print(*b)

Submission status: Accepted

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

ans = [0]*p

for i,j in enumerate(a):
    if j == 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: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

ans = [0]*p

for i,j in enumerate(a):
    if j == 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: Accepted

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
    I = [i for i, a in enumerate(A) if a]
    C = [a for a in A]

    for k in range(p):
        R[k] = V[k] * sum(C) % p

        for i in I:
            C[i] = C[i] * -i % p
    R[-1] = (R[-1] + len(I)) % p
    R.reverse()
    print(*R)
solve()

Submission status: Accepted

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

    B = [-i for i in range(p)]
    R = [0]*p
    I = [i for i, a in enumerate(A) if a]
    C = [a for a in A]

    for k in range(p):
        r = 0
        R[k] = V[k] * sum(C) % p

        for i in I:
            C[i] = C[i] * B[i] % p
    R[-1] += len(I)
    for k in range(p):
        R[k] %= p
    R.reverse()
    print(*R)
solve()

Submission status: Accepted

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

    C = [0]*p
    C[0] = 1
    zeros = [0]*p

    Y = [0]*p
    R = [0]*p
    for i in range(p):
        v = 0
        b = 1
        for j in range(i):
            v += Y[j] * b
            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]

        if i < p-1:
            C[1:] = ((b - a*i) % p for a, b in zip(C[1:], C))
            C[0] = 0
    for i in range(p):
        R[i] %= p
    print(*R)
solve()

Submission status: Accepted

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] %= 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: Accepted

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


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

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

    b = [0]*p
    for ai, av in enumerate(a):
        if av == 0:
            continue

        c = 1
        d = 1
        for i in range(p-1, -1, -1):
            b[i] += - c * d
            b[i] %= p
            c = c * i * inv[p-i] % p
            d = -d*ai % 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: Accepted

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

def modinv(a, m):
        b = m
        u = 1
        v = 0
        while b:
                t = a // b
                a -= t * b
                a, b = b, a
                u -= t * v
                u, v = v, u
        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
comb = []
for i in range(p):
    l = i
    r = p-1-i
    comb.append(-1 * inv_factorial[l] * inv_factorial[r] % p)

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

    ret[0] += 1
    temp = 1
    for j in range(p):
        ind = p-j-1
        if j > 0:
            temp *= (-i)
            temp %= p
        ret[ind] -= comb[ind] * temp
        ret[ind] %= p

print(*ret)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
p=int(input())
A=[int(i) for i in input().split()]
B=[0]*p
for i in range(p):
  a,c=A[i],1
  B[0]-=a
  for j in range(1,p):
    c=c*i%p
    B[j]-=a*c
    if j==p-1:
      B[j]+=a
B=B[::-1]
for i in range(p):
  B[i]=B[i]%p
print(*B)

Submission status: Accepted

Solution code:
p = int(input())
a = list(map(int,input().split()))
L = [0]*(p+1)
L[1] = 1
for n in range(1,p):
    for m in range(n+1,0,-1):
        L[m] = (L[m-1]-n*L[m])%p

fact = [1]*p
for n in range(1,p):
    fact[n] = n*fact[n-1]%p

factinv = [pow(m,p-2,p) for m in fact]

def Ln(n):
    res = [0]*p
    res[p-1] = 1
    for m in range(p-2,-1,-1):
        res[m] = (n*res[m+1]+L[m+1])%p
    res = [(1-2*((p-1-n)%2))*factinv[n]*factinv[p-1-n]*c%p for c in res]
    return res


ans = [0]*p
for n in range(p):
    if a[n] == 0:
        continue
    l = Ln(n)
    for m in range(p):
        ans[m] += l[m]
        ans[m] %= p

print(' '.join(str(c) for c in ans))

Submission status: Accepted

Solution code:
import numpy as np

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

bins = [1]
for i in range(1, p):
    bins.append(bins[-1] * (p - i) * pow(i, p - 2, p) % p)
bins = np.array(bins, dtype=np.int32)

pows_base = -np.arange(p, dtype=np.int32)
pows = np.zeros((p, p), dtype=np.int32)
pows[:, p - 1] = 1
for i in range(p - 2, -1, -1):
    pows[:, i] = pows[:, i + 1] * pows_base % p

coefs = np.zeros(p, dtype=np.int32)

for i, a in enumerate(aaa):
    if a == 0:
        continue

    coefs[0] += 1
    coefs = (coefs - bins * pows[i]) % p

print(*coefs)

Submission status: Accepted

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 = [0] * p
fact_inv[-1] = pow(fact[-1], p-2, p)
for i in range(p-2, -1 ,-1):
    fact_inv[i] = (fact_inv[i+1] * (i+1)) % 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
    k = 1
    for i in range(p-1, -1, -1):
        r_list[i] -= ncr[i] * k
        r_list[i] %= p
        k *= -j
        k %= p
    r_list[0] += 1

r_list[0] %= p
print(*r_list)

Submission status: Accepted

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

Fact=[1] #階乗
for i in range(1,p):
    Fact.append(Fact[i-1]*i%p)
Finv=[0]*p #階乗の逆元
Finv[-1]=pow(Fact[-1],p-2,p)
for i in range(p-2,-1,-1):
    Finv[i]=Finv[i+1]*(i+1)%p
def comb(n,r):
    if n<r:
        return 0
    return Fact[n]*Finv[r]*Finv[n-r]%p

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

Submission status: Accepted

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

import numpy as np
from numpy.fft import rfft, irfft
import itertools

P = int(input())
A = [int(x) for x in input().split()]

fft_len = 6144
def fft_convolve(A,B):
    C = irfft(rfft(A,fft_len) * rfft(B,fft_len))
    C = (C + .5).astype(np.int64)
    C[:P] += C[P:P+P]
    return C[:P] % P
  
one = np.array([1], dtype=np.int64)
arr = [np.array([(-x)%P,1],dtype=np.int64) for x in range(P)]
L = [one] + list(itertools.accumulate(arr[:-1],lambda a,b: np.convolve(a,b) % P))
R = ([one] + list(itertools.accumulate(arr[1:][::-1],lambda a,b: np.convolve(a,b) % P)))[::-1]
X = [fft_convolve(A,B) % P for A,B in zip(L,R)]

f = np.zeros(P,dtype=np.int64)
for a,x in zip(A,X):
    if a == 1:
        f -= x

f %= P
print(*f)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    print(max(a+b,a-b,a*b))
    return

#B
def B():
    k,x = LI()
    ans = []
    for i in range(x-k+1,x+k):
        ans.append(i)
    print(*ans)
    return

#C
def C():
    def f(s):
        res = [0]*m
        for i in s:
            res[alp.index(i)] += 1
        return res
    alp = list("abcdefghijklmnopqrstuvwxyz")
    m = len(alp)
    n = I()
    s = [input() for i in range(n)]
    d = defaultdict(lambda : 0)
    for i in s:
        d[tuple(f(i))] += 1
    ans = 0
    for i in d.values():
        ans += (i*(i-1))//2
    print(ans)
    return

#D
def D():
    n,m = LI()
    g = LIR(n)
    g.sort(key = lambda x:x[0])
    ans = 0
    f = [1]*n
    j = 0
    q = []
    for i in range(m)[::-1]:
        while j < n and m-g[j][0] >= i:
            a,b = g[j]
            heappush(q,(-b,a))
            j += 1
        if q:
            x,a = heappop(q)
            if i+a <= m:
                ans -= x
    print(ans)
    return

#E
def E():
    def dfs(x,f):
        for y,w in v[x]:
            if f[y]:
                if dp[y] < dp[x]+w:
                    f[y] = 0
                    dp[y] = dp[x]+w
                    dfs(y,f)
                    f[y] = 1
            else:
                if dp[y] < dp[x]+w:
                    dp[y] = float("inf")
                    dfs(y,f)
    n,m,p = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b,c = LI()
        a -= 1
        b -= 1
        v[a].append((b,c-p))
    f = [1]*n
    dp = [-float("inf")]*n
    dp[0] = 0
    f[0] = 0
    dfs(0,f)
    ans = dp[n-1]
    if ans == float("inf") or ans == -float("inf"):
        print(-1)
    elif ans < 0:
        print(0)
    else:
        print(ans)
    return

#F
def F():
    def comb(a,b):
        return fact[a]*inv[b]*inv[a-b]%p

    p = I()
    a = LI()
    fact = [1]
    for i in range(p-1):
        fact.append(fact[-1]*(i+1)%p)
    inv = [1]*p
    inv[p-1] = pow(fact[p-1],p-2,p)
    for i in range(1,p)[::-1]:
        inv[i-1] = inv[i]*i%p
    b = [0]*p
    for i in range(p):
        ai = a[i]
        if ai:
            b[0] += ai
            k = 1
            for j in range(p):
                c = ai*comb(p-1,j)*k%p
                k *= i
                if k >= p:
                    k %= p
                if j%2:
                    b[p-1-j] += c
                else:
                    b[p-1-j] -= c
                b[p-1-j] %= p
    print(*b)
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Accepted

Solution code:
p = int(input())
A = [[1]*p for _ in range(p)]
a = list(map(int,input().split()))
for n in range(p):
    for m in range(p-1):
        A[n][m+1] = n*A[n][m]%p

c = [0]*p
f = [1]*p

for n in range(1,p):
    f[n] = n*f[n-1]%p

for m in range(p):
    c[m] = f[p-1]*pow(f[m],p-2,p)*pow(f[p-1-m],p-2,p)%p

b = [0]*p

for n in range(p):
    if a[n] == 0:
        continue
    b[0] += 1
    b[0] %= p
    for m in range(p):
        b[m] -= A[n][p-1-m]*c[m]*(1-(m%2)*2)
        b[m] %= p

print(' '.join([str(x) for x in b]))