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:
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']
YNeos='YNeos'
mo=10**9+7
imp='IMPOSSIBLE'

p=I()
a=LI()
inv=[0]*p
for i in range(1,p):
    for j in range(1,p):
        if i*j%p==1:
            inv[i]=j
s=[0]*p        
for i in range(p):
    Q=1
    for j in range(p):
        if i==j:
            continue
        Q*=(i-j)
        Q%=p
    s[j]=(a[i]-Q)*inv[i]
    s[j]%=p
print(*s)

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):
        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 = 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):
        Ans[j+1] += Ans[j] * (-i) % P
    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:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from io import IOBase

import __pypy__


def mcrt(A, b, p):
    """returns x s.t. Ax = b mod p"""
    x = [0] * len(A)

    m = 1
    for i, Ai in enumerate(A):
        tot = sum(Ai[k] * x[k] for k in range(len(A)))
        tmp = (pow(Ai[-1], p - 2, p) * (b[i] - tot)) % p
        x[i] += tmp
        m *= p

    return [xi % p for xi in x]


def main():
    p = int(input())
    b = [int(x) for x in input().split()]
    A = [[0] * (p - 1) for _ in range(p - 1)]
    for i, Ai in enumerate(A):
        i += 1
        x = i
        for j in range(p - 1):
            Ai[j] = x
            x *= i
            x %= p

    print(*([b[0]] + mcrt(A, [b[i] - b[0] for i in range(1, p)], p)))


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0,
                              2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from io import IOBase

import __pypy__


def mcrt(A, b, p):
    """returns x s.t. Ax = b mod p"""
    piv = [p - 2] * (p - 1)
    x = [0] * len(A)

    m = 1
    for i, Ai in enumerate(A):
        tot = sum(Ai[k] * x[k] for k in range(len(A)))
        tmp = (pow(Ai[-1], p - 2, p) * (b[i] - tot)) % p
        x[piv[i]] += tmp * m
        m *= p

    return [xi % p for xi in x]


def main():
    p = int(input())
    b = [int(x) for x in input().split()]
    A = [[0] * (p - 1) for _ in range(p - 1)]
    for i, Ai in enumerate(A):
        i += 1
        x = i
        for j in range(p - 1):
            Ai[j] = x
            x *= i
            x %= p

    print(*([b[0]] + mcrt(A, [b[i] - b[0] for i in range(1, p)], p)))


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0,
                              2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


def pivot(A, p):
    """returns the pivot of A and m"""
    result = [0] * len(A)
    for i, Ai in enumerate(A):
        for j, Aij in enumerate(Ai):
            result[i] = j
    return result


def mcrt(A, b, p):
    """returns x s.t. Ax = b mod p"""
    piv = pivot(A, p)
    x = [0] * len(A)

    m = 1
    for i, Ai in enumerate(A):
        tot = sum(Ai[k] * x[k] for k in range(len(A)))
        tmp = (pow(m * Ai[piv[i]], p - 2, p) * (b[i] - tot)) % p
        x[piv[i]] += tmp * m
        m *= p
    return [xi % p for xi in x]


def main():
    p = int(input())
    b = [int(x) for x in input().split()]
    A = [[0] * (p - 1) for _ in range(p - 1)]
    for i, Ai in enumerate(A):
        i += 1
        x = i
        for j in range(p - 1):
            Ai[j] = x
            x *= i
            x %= p

    print(*([b[0]] + mcrt(A, [b[i] - b[0] for i in range(1, p)], p)))


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0,
                              2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


def pivot(A, p):
    """returns the pivot of A and m"""
    result = [0] * len(A)
    for i, Ai in enumerate(A):
        for j, Aij in enumerate(Ai):
            result[i] = j
    return result


def mcrt(A, b, p):
    """returns x s.t. Ax = b mod p"""
    piv = pivot(A, p)
    x = [0] * len(A)

    m = 1
    for i, Ai in enumerate(A):
        tot = sum(Ai[k] * x[k] for k in range(len(A)))
        tmp = (pow(m * Ai[piv[i]], p - 2, p) * (b[i] - tot)) % p
        x[piv[i]] += tmp * m
        m *= p
    return x


def main():
    p = int(input())
    b = [int(x) for x in input().split()]
    A = [[0] * (p - 1) for _ in range(p - 1)]
    for i, Ai in enumerate(A):
        i += 1
        x = i
        for j in range(p - 1):
            Ai[j] = x
            x *= i
            x %= p

    print(*([b[0]] + mcrt(A, [b[i] - b[0] for i in range(1, p)], p)))


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0,
                              2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#######################################
import numpy as np
import math
import copy
import re
import sys
#sys.exit(0)

inf = float("inf")
prime = 1

def check_print(check_flag, text, end="\n"):
  if check_flag:
    print(text, end=end)

def c2i(x):
    if str.isdecimal(x):
        return int(x)
    else:
        return x

def cout(*args):
  arglist = []
  for arg in args:
    if hasattr(arg, "__iter__"):
      arglist.extend(arg)
    else:
      arglist.append(arg)
      
  arglist = list(map(str, arglist))
  print(" ".join(arglist))
  
def count2(num):
  count=0
  while num%2==0:
    num/=2
    count+=1
  return count

def ketasum(num):
  nums = [int(s) for s in str(num)]
  return sum(nums)

#math
def gcd(a, b): #最大公約数
  while b:
    a, b = b, a % b
  return a

def lcm(a, b): #最小公倍数
  return a * b // gcd (a, b)

def gcd3(lis): #最大公約数(3over)
  ans = lis[0]
  for li in lis:
    ans = gcd(ans,li)

def lcm3(lis): #最小公倍数(3over)
  ans = lis[0]
  for li in lis:
    ans = lcm(ans,li)

def divisor(n): #nの約数を全て求める
  i = 1
  table = []
  while i * i <= n:
    if n%i == 0:
      table.append(i)
      table.append(n//i)
    i += 1
  table = list(set(table))
  return table

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table

def is_prime(n):
  for i in range(2, n + 1):
    if i * i > n:
      break
    if n % i == 0:
      return False
  return n != 1

#input stock
"""
n = int(input())

#list
a = map(int, input().split())
a,b = map(int, input().split())

d=[]
for i in range(n):
  d[i]=int(input())

#2dim-list
a = [list(map(int, input().split())) for i in range(n)]

s = input()
ss =  [int(si) for si in s]
"""

#processing stock
"""
a = sorted(a)
a = sorted(a, reverse=True)

"""

#regex
"""
pattern = ""
result = re.search(pattern, s)

result = re.fullmatch(pattern, s)

result = re.finditer(pattern, s)
for res in result:
    print res.group()   # 1回目: ca      2回目: ca   
    print res.start()   # 1回目: 0       2回目: 6      
    print res.end()     # 1回目: 2       2回目: 8      
    print res.span()    # 1回目: (0, 2)  2回目: (6, 8)
"""

#######################################
p = int(input())
a = list(map(int, input().split()))
b = [0]*p

for i in range(p):
  if i==0:
    b[i] = a[i]
  else:
    tmp = 0
    for j in range(i):
      tmp += i**j * b[j]
    
    c = 0
    while True:
      b[i] = int((a[i] + p*c - tmp) / (i**i))
      if 0 <= b[i] and b[i]<=(p-1):
        break
      else:
        c+=1  
    
cout(b)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

### 素数の逆元とCombination

M = p
N = 10**4 # 必要なテーブルサイズ

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 

def cmb(n, r, M):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return (g1[n] * g2[r] * g2[n-r]) % M
ans = [0]*p
for i,num in enumerate(a):
    if num==0:
        continue
    for j in range(p):
        ans[j] += -cmb(p-1,j,M) * pow(-i,p-1-j)
    ans[0] += 1
for i in range(p):
    ans[i] %= M
write(" ".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
# AC 回避した https://atcoder.jp/contests/abc137/submissions/6845103 の再提出

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()))
ans = lagrange_interpolation(list(range(p)), A, p)
print(" ".join(map(str, ans[::-1])))

Submission status: Time Limit Exceeded

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

Q = [1 for _ in range(P)]

for i in range(P):
    if A[i]:
        for k in range(P):
            if i == k:
                continue
            Q[i] *= pow(i - k, P - 2, P)
            Q[i] %= P
    else:
        Q[i] = 0

F = [0 for _ in range(P + 1)]
F[0] = 1

for i in range(P):
    tmp = [0 for _ in range(P + 1)]
    for j in range(1, P + 1):
        tmp[j] += F[j - 1]
        tmp[j] %= P
    for j in range(P + 1):
        tmp[j] += F[j] * (-i)
        tmp[j] %= P
    F = tmp

res = [0 for _ in range(P)]

for i in range(P):
    G = [0 for _ in range(P)]
    G[P - 1] = F[P]
    res[P - 1] += Q[i] * G[P - 1]
    res[P - 1] %= P
    for j in range(P - 1)[::-1]:
        G[j] = F[j + 1] + i * G[j + 1]
        G[j] %= P
        res[j] += Q[i] * G[j]
        res[j] %= P

print(*res)

Submission status: Time Limit Exceeded

Solution code:
class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def C(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def P(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod


P = int(input())
c = Combi(P-1, P)
A = list(map(int,input().split()))
ans = [0 for i in range(P)]
for i in range(P):
    if A[i] != 0:
        ans[0] += 1
        for j in range(P):
            ans[j] -= c.C(P-1, j)*pow(-i, P-1-j,P) 
for i in range(P):
    ans[i] %= P
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


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


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


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

is_0 = []
is_1 = []

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

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


G_que = []

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def ext_euc(a, b):
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euc(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    x, _, _ = ext_euc(a, mod)
    return x % mod


def main():
    p = int(input())
    A = list(map(int, input().split()))
    # comb(p - 1, i)
    comb = [1] * p
    for i in range(1, p):
        v = comb[i - 1]
        v *= p - i
        v *= mod_inv(i, p)
        comb[i] = v % p
    b = [0] * p
    for k, a in enumerate(A):
        if a == 0:
            continue
        pw = [1] * p  # (- k)**(p - 1 - i)
        for i in range(1, p):
            pw[- (i + 1)] = (pw[- i] * (- k)) % p
        for i in range(p):
            if i == 0:
                b[i] += 1
            b[i] -= comb[i] * pw[i]
            b[i] %= p
    print(' '.join(map(str, b)))            


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

fact_list=[1]
fact_inv_list=[1]
for i in range(1,p):
  fact=(fact_list[-1]*i)%p
  fact_list.append(fact)
  fact_inv_list.append(pow(fact,p-2,p))
def comb_mod(n,r):
  return fact_list[n]*fact_inv_list[r]*fact_inv_list[n-r]
  
answer_list=[0]*p
for i in range(p):
  a=alist[i]
  if a==1:
    #1-(x-i)^(p-1)
    coeff_list=[0]*p
    coeff_list[0]=1
    for j in range(p):
      coeff=comb_mod(p-1,j)*pow(-i,p-1-j,p)
      coeff_list[j]-=coeff
      coeff_list[j]%=p
      
    #print(i,coeff_list)
    for i in range(p):
      answer_list[i]+=coeff_list[i]
      answer_list[i]%=p
      
print(*answer_list)

Submission status: Time Limit Exceeded

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

MOD = p
MAX = p + 10
fact = [1] * (MAX + 1)  # i!
finv = [1] * (MAX + 1)  # (i!)^{-1}
iinv = [1] * (MAX + 1)  # i^{-1}
for i in range(2, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * iinv[i] % MOD


def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n - k] % MOD


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

print(*b)

Submission status: Time Limit Exceeded

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

p = int(input())
A = tuple(map(int, input().split()))
B = [0]*p
U = p-1
MOD = p
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z

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

Submission status: Time Limit Exceeded

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

p = int(input())
A = tuple(map(int, input().split()))
B = [0]*p
U = p-1
MOD = p
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z

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

Submission status: Time Limit Exceeded

Solution code:
P = int(input())
A = [int(_) for _ in input().split()]


class Factorial:
    def __init__(self, max_fact, mod):
        #mod should be prime number
        #using homogeneous_product(n,r), max_fact ≧ max(n+r-1)
        f = [1] * (max_fact + 1)
        for idx in range(2, max_fact + 1):
            f[idx] = f[idx - 1] * idx
            f[idx] %= mod
        fi = [pow(f[-1], mod - 2, mod)]
        for idx in range(max_fact, 0, -1):
            fi += [fi[-1] * idx % mod]
        fi = fi[::-1]
        self.mod = mod
        self.f = f
        self.fi = fi

    def factorial(self, n):
        return self.f[n]

    def factorial_inverse(self, n):
        return self.fi[n]

    def combination(self, n, r):
        f = self.f
        fi = self.fi
        return f[n] * fi[r] * fi[n - r] % self.mod

    def permutation(self, n, r):
        return self.f[n] * self.fi[n - r] % self.mod

    def homogeneous_product(self, n, r):
        f = self.f
        fi = self.fi
        return f[n + r - 1] * fi[r] * fi[n - 1] % self.mod


max_fact = P - 1
mod = P
fact_instance = Factorial(max_fact, mod)
comb = fact_instance.combination
perm = fact_instance.permutation
combrep = fact_instance.homogeneous_product

ans = [0] * P
for i, a in enumerate(A):
    if a:
        #1-(x-i)^(P-1)
        ans[0] += 1
        for r in range(P):
            ans[r] -= comb(P - 1, r) * pow(-i, P - 1 - r, P)
            ans[r] %= mod
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
P = int(input())
A = [int(_) for _ in input().split()]


class Factorial:
    def __init__(self, max_fact, mod):
        #mod should be prime number
        #using homogeneous_product(n,r), max_fact ≧ max(n+r-1)
        f = [1] * (max_fact + 1)
        for idx in range(2, max_fact + 1):
            f[idx] = f[idx - 1] * idx
            f[idx] %= mod
        fi = [pow(f[-1], mod - 2, mod)]
        for idx in range(max_fact, 0, -1):
            fi += [fi[-1] * idx % mod]
        fi = fi[::-1]
        self.mod = mod
        self.f = f
        self.fi = fi

    def factorial(self, n):
        return self.f[n]

    def factorial_inverse(self, n):
        return self.fi[n]

    def combination(self, n, r):
        f = self.f
        fi = self.fi
        return f[n] * fi[r] * fi[n - r] % self.mod

    def permutation(self, n, r):
        return self.f[n] * self.fi[n - r] % self.mod

    def homogeneous_product(self, n, r):
        f = self.f
        fi = self.fi
        return f[n + r - 1] * fi[r] * fi[n - 1] % self.mod


max_fact = P - 1
mod = P
fact_instance = Factorial(max_fact, mod)
comb = fact_instance.combination
perm = fact_instance.permutation
combrep = fact_instance.homogeneous_product

ans = [0] * P
for i, a in enumerate(A):
    if a:
        #1-(x-i)^(P-1)
        ans[0] += 1
        for r in range(P):
            ans[r] -= comb(P - 1, r) * pow(-i, P - 1 - r, P)
print(*[j % P for j in ans])

Submission status: Time Limit Exceeded

Solution code:
class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def inverse(self, k):
        """kの逆元を求める O(1)"""
        return (self.inv_fact[k] * self.fact[k - 1]) % self.MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

    def combination2(self, k, r):
        """kCrを求める O(r)
        kが大きいが、r <= nを満たしているときに使用
        """
        if k < r:
            return 0
        res = 1
        for l in range(r):
            res *= (k - l)
            res %= self.MOD
        return (res * self.inv_fact[r]) % self.MOD


p = int(input())
a = list(map(int, input().split()))
comb = Combination(p - 1, p)


b = [0] * p
for i in range(p):
    for j in range(p):
        # (x - j) ^ (p - 1) の係数x^iの部分
        tmp = ((-j) ** (p - 1 - i)) * comb.combination(p - 1, i)
        b[i] -= a[j] * tmp
        b[i] %= p
b[0] = a[0]

print(*b)

Submission status: Time Limit Exceeded

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

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

# コンビネーション
mod = P
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NN = 10**5 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, NN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ans = [0]*P
for j, a in enumerate(A):
    if a == 1:
        ans[0] = (ans[0] + 1) % P
        for k in range(P):
            ans[P-1-k] = (ans[P-1-k] - cmb(P-1, k) * pow(j, k, P) * (-1)**k) % P
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
p = int(input())
a = list(map(int,input().split()))
mod = p
rng = 10100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def inv(x):
  return pow(x,mod-2,mod)
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
ans = [0]*p
for i in range(p):
  if a[i]:
    ans[0] += 1
    for j in range(p):
      ans[-j-1] -= ((-1)**(j%2))*cmb(p-1,j)*pow(i,j,p)
      ans[-j-1] %= mod
print(*ans)