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:
import sys
mod = pow(10, 9) + 7
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 = (10**5)
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 )
P = int(input())
As = list(map(int, input().split()))
rs = [0]*P

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

Submission status: Wrong Answer

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

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

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

print(*b)

Submission status: Wrong Answer

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

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

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


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

Submission status: Wrong Answer

Solution code:
import os
import sys
import numpy as np

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

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


# MOD = 998244353


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


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


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


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

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


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


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


def power_table():
    ret = np.ones((P, P), dtype=int)
    row = -np.arange(P, dtype=int)
    for i in range(1, P):
        ret[i] = ret[i - 1] * row
    return ret


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

B = np.zeros(P, dtype=int)
for j, a in enumerate(A):
    if a == 0:
        continue
    B -= power[:, j] * ncr % P
    B[-1] += 1
    B %= P
print(*B[::-1])

Submission status: Wrong Answer

Solution code:
import os
import sys

import numpy as np

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

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


# MOD = 998244353


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


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


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


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

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


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

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


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

Submission status: Wrong Answer

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

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

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, MOD)


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

Solution code:
p = int(input())
A = list(map(int, input().split()))
comb = [0]*p
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: Wrong Answer

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-1))%p
    c += 1
for j in b_list:
    print(j % p,end = ' ')

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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(1,p):
        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: Wrong Answer

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(1,p):
        Pow[i][0] = i
    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: Wrong Answer

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

Submission status: Wrong Answer

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
        s = 1
        for j in range(p):
            b[j] -= comb(p - 1, j) * s
            b[j] %= MOD
            s *= -i
            s %= MOD

print(*b)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

ans = [0]*p
ans = np.zeros(p,dtype=np.int64)

ind = [p-1-i for i in range(p)]

for j in b:
    ans = ans - np.power(j,ind)
    ans = np.mod(ans,p)

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

ans = np.mod(ans,p)

print(*ans)

Submission status: Wrong Answer

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)
    comb = [combination.combination(P - 1, i) % P 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: Wrong Answer

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)
    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 = ((tmp % P) + P) % P
            ans[index] -= comb[index] * tmp
            ans[index] = ((ans[index] % P) + P) % 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: Wrong Answer

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

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

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)
    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 の係数から各々引く
        ans[0] += 1
        for k in range(P):
            index = P - k - 1
            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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
p=int(input())
A=[int(i) for i in input().split()]
B=[0]*p

P=[[0]*p for _ in range(p)]
for i in range(1,p): 
  for j in range(p):
    if j==0:
      P[i][j]=i
    else:
      P[i][j]=(P[i][j-1]*i)%p
PP=[0]*p
for i in range(1,p):
  for j in range(1,p):
    PP[j]=(PP[j]+P[i][j])%p
for i in range(p):
  a=A[i]
  B[0]-=a
  for j in range(1,p):
    B[j]-=a*PP[j]
    if j==p-1:
      B[j]+=a
B=B[::-1]
for i in range(p):
  B[i]%=p
print(*B)

Submission status: Wrong Answer

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


print(*r_list)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

import numpy as np

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

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

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

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

Submission status: Wrong Answer

Solution code:
P = int(input())
A = list(map(int, input().split()))
Ans = [0] * (P+1)
Ans[0] = A[0]
for i, a in enumerate(A[1:], 1):
    #print(Ans)
    for j in range(i-1, -1, -1):
        Ans[j+1] += Ans[j] * (-i) % P
    Ans[i] += a
for i in range(P+1):
    Ans[i] %= P
#print(Ans)
Ans.reverse()
print(*Ans[1:])

Submission status: Wrong Answer

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


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

frac, fraci = frac(p)



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

C = [0]*p
for i in range(p):
    a = A[i]
    for j in range(i):
        a = (a-C[j]*frac[i]*fraci[i-j])
    C[i] = fraci[i]*a%p

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

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

Submission status: Wrong Answer

Solution code:
P = int(input())
A = list(map(int, input().split()))
Ans = [0] * (P+1)
Ans[0] = A[0]
for i, a in enumerate(A[1:], 1):
    #print(Ans)
    for j in range(i-1, -1, -1):
        Ans[j+1] += Ans[j] * (-i)
    Ans[i+1] += a
for i in range(P+1):
    Ans[i] %= P
#print(Ans)
Ans.reverse()
print(*Ans[1:])

Submission status: Wrong Answer

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

x = 1

b = [0] * p
s = 0
for i in range(1, p):
    for b_i in range(p):
        if (pow(b_i, i) + s) % p == a[i]:
            b[i] = b_i
            break
    s += b[i] * x
    s %= p

print(*b)