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 numpy as np
mod = 998244353

def poly_mul(f, g):
    # 参考: https://judge.yosupo.jp/submission/2380
    Lf = len(f); Lg = len(g); L = Lf + Lg - 1
    if Lf <= 16 or Lg <= 16:
        if Lf == 0 or Lg == 0:
            return np.zeros((0,), dtype=np.int64)
        return (np.convolve(f.astype(np.uint64), g.astype(np.uint64)) % mod).astype(np.int64)
    fft = np.fft.rfft; ifft = np.fft.irfft
    fft_len = 1 << L.bit_length()
    fl = f & (1 << 15) - 1; fh = f >> 15
    gl = g & (1 << 15) - 1; gh = g >> 15
    x = (ifft(fft(fl, fft_len) * fft(gl, fft_len))[:L] + 0.5).astype(np.int64) % mod
    y = (ifft(fft(fl+fh, fft_len) * fft(gl+gh, fft_len))[:L] + 0.5).astype(np.int64) % mod
    z = (ifft(fft(fh, fft_len) * fft(gh, fft_len))[:L] + 0.5).astype(np.int64) % mod
    return (x + ((y - x - z) << 15) + (z << 30)) % mod

def poly_inv(fps, n=None):
    assert fps[0] != 0
    if n is None:
        n = len(fps)
    res = np.zeros(1<<(n-1).bit_length(), dtype=np.int64)
    res[0] = pow(int(fps[0]), mod-2, mod)
    i = 1
    while i < n:
        i <<= 1
        res[:i] = ((res[:i]<<1) - poly_mul(poly_mul(res[:i>>1], res[:i>>1]), fps[:i])[:i]) % mod
    return res[:n]

def poly_div(fps1, fps2):
    n1, n2 = len(fps1), len(fps2)
    if n1 < n2:
        return np.zeros((0,), dtype=np.int64)
    n = n1 - n2 + 1
    res = poly_mul(fps1[-1:-n-1:-1], poly_inv(fps2[::-1], n))[n-1::-1]
    return res

def poly_mod(fps1, fps2):
    n1, n2 = len(fps1), len(fps2)
    if n1 < n2:
        return fps1
    res = fps1[:n2-1] - poly_mul(poly_div(fps1, fps2), fps2)[:n2-1]
    return res % mod

def multipoint_evaluation(fps, xs):
    threshold = 8
    n_xs = len(xs)
    bit = (n_xs-1).bit_length()
    if bit <= threshold:
        res = np.zeros_like(xs)
        xs_cumprod = np.ones_like(xs)
        for coef in fps:
            res += xs_cumprod * coef
            xs_cumprod *= xs
            xs_cumprod %= mod
        return res
    k = 1<<bit
    fpss = np.zeros((bit+1, k+1), dtype=fps.dtype)
    fpss[0, :n_xs] = -xs % mod
    fpss[1, :k:2] = fpss[0, :k:2] * fpss[0, 1::2] % mod
    fpss[1, 1::2] = (fpss[0, :k:2] + fpss[0, 1::2]) % mod
    for i in range(1, bit):
        step = 2<<i
        half = step>>1
        for j in range(0, k, step):
            f1 = fpss[i, j:j+half+1].copy()
            f2 = fpss[i, j+half:j+step+1].copy()
            f1[-1] = f2[-1] = 1
            f = poly_mul(f1, f2)
            fpss[i+1, j:j+step] = f[:-1]
    f = poly_mod(fps, f)
    fpss[-1, :len(f)] = f
    fpss[-1, len(f):] = 0
    for i in range(bit-1, threshold-1, -1):
        step = 2<<i
        half = step>>1
        for j in range(0, k, step):
            f = fpss[i+1, j:j+step]
            f1 = fpss[i, j:j+half+1].copy()
            f2 = fpss[i, j+half:j+step+1].copy()
            f1[-1] = f2[-1] = 1
            fpss[i, j:j+half] = poly_mod(f, f1)
            fpss[i, j+half:j+step] = poly_mod(f, f2)
    xs = (-fpss[0, :k] % mod).reshape(-1, 1<<threshold)
    xs_cumprod = np.ones_like(xs)
    res = np.zeros_like(xs)
    for i in range(1<<threshold):
        res += fpss[threshold, i:k:1<<threshold, None] * xs_cumprod % mod
        xs_cumprod *= xs
        xs_cumprod %= mod
    return res.reshape(-1)[:n_xs] % mod

def poly_differential(fps):
    return fps[1:] * np.arange(1, len(fps)) % mod

def lagrange_interpolation(X, Y, mod):
    # old
    n = len(X)
    g = [0]*(n+1)
    g[0] = 1
    for i, x in enumerate(X):
        for j in range(i, -1, -1):
            g[j+1] += g[j] * (-x) % mod
    res = [0]*n
    for x, y in zip(X, Y):
        f = g[:]
        denom = 0
        v = 1
        pow_x = [1]  # x の idx 乗
        for _ in range(n-1):
            v = v * x % mod
            pow_x.append(v)
        pow_x.reverse()  # n-1 乗 ~ 0 乗
        for i, po in enumerate(pow_x):
            f_i = f[i]
            f[i+1] += f_i * x % mod  # f = g / (x - x_i) を組立除法で求める
            denom = (denom + f_i * po) % mod
        denom_inv = pow(denom, mod-2, mod)
        for i, f_i in enumerate(f[:n]):
            res[i] += (f_i * y * denom_inv)# % mod  # mod が大きいと 64bit に収まらなくなるのでひとつずつ mod 取った方がいいか？
    return [v % mod for v in res]

def polynomial_interpolation(xs, ys):
    # 参考: https://rsk0315.hatenablog.com/entry/2020/04/05/203210
    assert len(xs) == len(ys)
    threshold = 8
    as_strided = np.lib.stride_tricks.as_strided
    n = len(xs)
    if n==1:
        return ys.copy()
    bit = (n-1).bit_length()
    if bit <= threshold:
        res = lagrange_interpolation(xs.tolist(), ys.tolist(), mod)
        return np.array(res[::-1], dtype=np.int64)
    k = 1<<bit
    fpss = np.zeros((bit+1, n+1), dtype=np.int64)
    fpss[0, :n] = -xs % mod
    for i in range(bit):
        step = 2 << i
        half = step >> 1
        for j in range(0, n, step):
            if j+half >= n:
                fpss[i+1, j:n] = fpss[i, j:n]
                continue
            f1 = fpss[i, j:j+half+1].copy()
            f2 = fpss[i, j+half:j+step+1].copy()
            f1[-1] = f2[-1] = 1
            f = poly_mul(f1, f2)
            fpss[i+1, j:j+len(f)-1] = f[:-1]
    fpss2 = np.zeros((bit+1, k+1), dtype=np.int64)
    fpss2[bit, :n] = poly_differential(f)
    for i in range(bit-1, threshold-1, -1):
        step = 2<<i
        half = step>>1
        for j in range(0, n, step):
            if j+half >= n:
                fpss2[i, j:n] = fpss2[i+1, j:n]
                continue
            f = fpss2[i+1, j:min(j+step, n)]
            f1 = fpss[i, j:j+half+1].copy()
            f2 = fpss[i, j+half:min(j+step, n)+1].copy()
            f1[-1] = f2[-1] = 1
            fpss2[i, j:j+half] = poly_mod(f, f1)
            fpss2[i, j+half:min(j+step, n)] = poly_mod(f, f2)
    xs = as_strided(xs, (k>>threshold, 1<<threshold), (8<<threshold, 8))
    xs_cumprod = np.ones_like(xs)
    f = np.zeros_like(xs)
    for i in range(1<<threshold):
        f += fpss2[threshold, i:k:1<<threshold, None] * xs_cumprod % mod
        xs_cumprod *= xs
        xs_cumprod %= mod
    f = f.ravel()
    for j in range(n):
        fpss2[0, j] = ys[j] * pow(int(f[j]), mod-2, mod) % mod
    for i in range(bit):
        step = 2 << i
        half = step >> 1
        for j in range(0, k, step):
            if j+half >= n:
                fpss2[i+1, j:n] = fpss2[i, j:n]
                continue
            f1 = fpss[i, j:j+half+1].copy()
            f2 = fpss[i, j+half:j+step+1].copy()
            f1[-1] = f2[-1] = 1
            fpss2[i+1, j:min(j+step, n)] = (
                poly_mul(fpss2[i, j:j+half], f2)
                + poly_mul(fpss2[i, j+half:min(j+step, n)], f1)
            ) % mod
    return fpss2[bit, :n]

mod = int(input())
A = np.array(input().split(), dtype=np.int64)
X = np.arange(mod, dtype=np.int64)
Ans = polynomial_interpolation(X, A)
print(" ".join(map(str, Ans.tolist())))

Submission status: Accepted

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

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

for i in range(P):
    if A[i]:
        for k in range(P):
            if i == k:
                continue
            Q[i] *= (i - k)
            Q[i] %= P
        Q[i] = pow(Q[i], P - 2, 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: Accepted

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()))
power=[1 for i in range(P)]
ans = [0 for i in range(P)]
for i in range(P):
    if A[i] != 0:
        ans[0] += 1
        power[0]
        for  _ in range(1,P):
            power[_]=power[_-1]*(-i)%P
        for j in range(P):
            ans[j] -= c.C(P-1, j)*power[P-1-j] 
for i in range(P):
    ans[i] %= P
print(*ans)

Submission status: Accepted

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

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    p = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    mod = p
    maxn=p
    fact=[1]*(maxn+1)#NはnCrの最大のn
    invs=[1]*(maxn+1);invs[0]=0
    ifact=[1]*(maxn+1)
    for i in range(2,maxn+1):
        fact[i]=(fact[i-1]*i)%mod
        invs[i]=invs[mod%i]*(-(mod//i))%mod
        ifact[i]=(ifact[i-1]*invs[i])%mod
    def perm(n,r): return fact[n]*ifact[n-r]%mod
    def comb(n,r): return (fact[n]*ifact[r]%mod)*ifact[n-r]%mod
    def multicomb(self,n,*rs):#n!/(r1!*r2!*r3!*...)
        ans=fact[n]
        for r in rs: ans=(ans*self.ifact[r])%self.mod
        return ans
    
    tot=[0]*p
    tot[0]=sum(A)%mod
    for i in range(p):
        a=A[i]
        if not a:
            continue
        #sgn=pow(-1,p-1)
        mi=(-i)%mod
        base=pow(mi,p-1,mod)
        
        for j in range(p):
            if j==p-1:
                base=1
            tot[j]-=base*comb(p-1,j)%mod
            tot[j]%=mod
            base*=invs[mi]
            base%=mod

    
    print(*tot)


if __name__ == "__main__":
    main()

Submission status: Accepted

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_list[j]-=comb_mod(p-1,j)*pow(-i,p-1-j,p)
      
    #print(i,coeff_list)
    for i in range(p):
      answer_list[i]+=coeff_list[i]
      
for i in range(p):
  answer_list[i]%=p

print(*answer_list)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
p = int(readline())
a = list(map(int,readline().split()))

MAX = 3000
fact = [1]*(MAX+1)
for i in range(1, MAX+1):
    fact[i] = (fact[i-1]*i) % p

inv = [1]*(MAX+1)
for i in range(2, MAX+1):
    inv[i] = inv[p % i]*(p-p//i) % p

fact_inv = [1]*(MAX+1)
for i in range(1, MAX+1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % p

def comb(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[n-k] * fact_inv[k] % p

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

Submission status: Accepted

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

MAX = 3000
fact = [1]*(MAX+1)
for i in range(1, MAX+1):
    fact[i] = (fact[i-1]*i) % p

inv = [1]*(MAX+1)
for i in range(2, MAX+1):
    inv[i] = inv[p % i]*(p-p//i) % p

fact_inv = [1]*(MAX+1)
for i in range(1, MAX+1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % p

def comb(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[n-k] * fact_inv[k] % p

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

Submission status: Accepted

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) % 2)
            b[k] %= MOD

print(*b)

Submission status: Accepted

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 = pow(-j, (p - 1 - i), p) * comb.combination(p - 1, i)
        b[i] -= a[j] * tmp
        b[i] %= p
b[0] = a[0]

print(*b)

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

p = I()
a = LI()

# iで1,i以外で0をとる多項式は 1-(x-i)**(p-1)
# これらを足し合わせればよい

C = [1]
for i in range(1,p):
    C.append((C[-1]*(p-i)*pow(i,p-2,p)) % p)
# C[i] = (p-1)_C_i

ANS = [a[0]]
for i in range(1,p):
    s = -C[i] % p
    t = sum(a[j]*pow(-j,p-1-i,p) for j in range(p)) % p
    ANS.append((s*t) % p)

print(*ANS)

Submission status: Accepted

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


def main():
    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
            t = 1
            for k in range(P):
                ans[P-1-k] = (ans[P-1-k] - cmb(P-1, k) * t) % P
                t = t * (-j) % P
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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
    const = 1
    for j in range(p):
      ans[-j-1] -= ((-1)**(j%2))*cmb(p-1,j)*const
      ans[-j-1] %= mod
      const *= i
      const %= mod
print(*ans)

Submission status: Accepted

Solution code:
p = int(input())


def div(a, b):
    n = len(a)
    m = len(b)
    res = [0] * (n - m + 1)
    tmp = pow(b[-1], p - 2, p)
    for i in range(n - m, -1, -1):
        t = a[i + m - 1] * tmp % p
        res[i] = t
        for j in range(m):
            a[i + j] = (a[i + j] - t * b[j]) % p
    return res


a = list(map(int, input().split()))
ans = [0] * p
f = [0] * (p + 1)
f[0] = 1
for i in range(p):
    for j in range(p, 0, -1):
        f[j] += f[j - 1]
        f[j - 1] = -f[j - 1] * i
        f[j] %= p
for i in range(p):
    if a[i] == 1:
        fm = div(f[:], [-i, 1])
        t = 1
        r = 0
        for v in fm:
            r += v * t
            t = t * i % p
        t = pow(r, p - 2, p)
        for j in range(len(fm)):
            ans[j] += fm[j] * t
for i in range(p):
    ans[i] %= p
print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.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

def solve():
    def lagrange_interpolation(x,y,mod=mod):
        n = len(x)-1
        dp = [0]*(n+2)
        dp[0] = x[0]
        dp[1] = 1
        for i in range(n):
            nd = [0]*(n+2)
            ni = i+1
            for j in range(n+2):
                nj = j
                nd[nj] += -x[ni]*dp[j]
                nd[nj] %= mod
                if j <= n:
                    nj = j+1
                    nd[nj] += dp[j]
                    nd[nj] %= mod
            for j in range(n+2):
                dp[j] = nd[j]

        f = [0]*(n+1)
        for i in range(n+1):
            if y[i] == 0:
                continue
            fi = 1
            for j in range(n+1):
                if i == j:
                    continue
                fi *= x[i]-x[j]
                fi %= mod
            fi = pow(fi,mod-2,mod)
            p = [0]*(n+1)
            if x[i] == 0:
                for j in range(n+1):
                    p[j] = dp[j+1]
            else:
                inv = pow(x[i],mod-2,mod)
                p[0] = -dp[0]*inv%mod
                for j in range(1,n+1):
                    p[j] = (p[j-1]-dp[j])*inv%mod
            for j in range(n+1):
                f[j] += y[i]*fi*p[j]
                f[j] %= mod
        return f
    p = I()
    a = LI()
    f = lagrange_interpolation(list(range(p)),a,p)
    print(*f)
    return

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    ans = [0] * p
    for i, a in enumerate(A):
        if not a:
            continue
        ans[-1] += 1
        ij = 1
        ans[0] = (ans[0] - ij)%p
        for j in range(1, p):
            ij = (ij * i)%p
            ans[j] = (ans[j] - ij)%p
    ans.reverse()
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

p = int(input())

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

lis = [0] * (p+1)

for i in range(p):

    if i == 0:
        lis[1] = 1
        lis[0] = 0

    else:
        
        nlis = [0] * (p+1)

        for j in range(p+1):
            nlis[j] += lis[j] * (-1 * i)
            if j != 0:
                nlis[j] += lis[j-1]
            nlis[j] %= p

        lis = nlis

#print (lis) = (x-0)*(x-1)*…*(x-p+1)の各項の係数
#ラグランジュ補完を実際に計算していく
#参考　https://mathtrain.jp/hokan

ans = [0] * p

for i in range(p):

    #fi(x)を計算 (x-i)でlisを割る
    if a[i] == 0:
        continue

    nlis = [0] * p

    for j in range(p-1,-1,-1):

        if j == p-1:
            nlis[j] = lis[j+1]
        else:
            nlis[j] = (lis[j+1] - nlis[j+1] * (-1 * i)) % p

    for j in range(p):
        ans[j] += nlis[j]

for i in range(p):
    ans[i] = (p - ans[i]) % p
print (" ".join(map(str,ans)))

Submission status: Accepted

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

#よくある補間だとiごとにO(p)次多項式をx-j倍する操作が入ってO(p**3),間に合わない

#editorial
#1-(x-j)**(p-1)

ans = [0 for _ in range(p)]

chs = [1]

deno = 1
nume = 1

for i in range(1,p):
    nume*=p-i
    deno *= pow(i,p-2,p)
    chs.append(nume*deno%p)

#pow使っていたの修正
for i in range(p):
    tmp = 1
    if not a[i]:
        continue
    for j in range(p):
        ans[p-1-j] -= chs[p-1-j]*tmp
        tmp *= p-i
        tmp %= p
    ans[0]+=1
    

for i in range(p):
    ans[i]%=p 


print(*ans)

Submission status: Accepted

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

list_size = p-1

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % p)

f_r_list[-1] = pow(f_list[-1], p - 2, p)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % p)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % p) * f_r_list[r - 1]) % p 

pows = [[1] for x in range(p)]
for i in range(p):
	for _ in range(p-1):
		pows[i].append((pows[i][-1] * i) % p)

ans = [0 for _ in range(p)]
for i, x in enumerate(a):
	if x == 0:
		continue
	ans[0] += 1
	ans[0] %= p
	for j in range(p):
		ans[j] -= pows[(p-i)%p][p-1-j] * comb(p-1, j)
		ans[j] %= p

print(*ans)

Submission status: Accepted

Solution code:
p=int(input())
A=list(map(int,input().split()))
cmb=[0]*p
cmb[0]=1
for i in range(1,p):
  cmb[i]=cmb[i-1]*(p-i)*pow(i,p-2,p)%p
ans=[0]*p
for i in range(p):
  if A[i]==1:
    b=1
    ans[0]=ans[0]+1
    for j in range(p):
      ans[p-j-1]=(ans[p-j-1]-cmb[j]*b)%p
      b=b*(-i)%p
for i in range(p-1):
  print(ans[i],end=" ")
print(ans[p-1])

Submission status: Accepted

Solution code:
import sys
P = int(input())
As = list(map(int, input().split()))
rs = [0]*P
mod = P
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))

def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = 3000
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
C = []
for i in range(P):
    C.append(cmb(P-1, i))


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

Submission status: Accepted

Solution code:
p = int(input())
a = list(map(int,input().split()))
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)
powl = [[1]*(p+1) for _ in range(p+1)]
for i in range(p+1):
    for j in range(p):
        powl[i][j+1] = (i*powl[i][j])%p

for i in range(1,p):
    k1 = powl[i][p-2]
    k2 = powl[p-1][p-1-i]
    if a[i]==1:
        for j in range(1,p):
            kj = powl[k1][j]
            b[j] += kj*k2*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: Accepted

Solution code:

def poly_divide(f, g):
    n = len(g)
    a, b = f
    q = [0]*(n-1)
    r = 0
    q[-1] = g[-1]*inv[b%p]%p
    for i in range(n-2)[::-1]:
        q[i] = (g[i+1]-q[i+1]*a)*inv[b%p]%p
    r = g[0]-q[0]
    return q, r
  
def poly_product(f, g):
    n, m = len(f), len(g)
    res = [0]*(n+m-1)
    for i in range(n):
        for j in range(m):
            res[i+j]+=g[j]*f[i]
            res[i+j]%=p
    return res
def assign(f, x):
    tmp = 1
    res = 0
    n = len(f)
    for i in range(n):
        res+=f[i]*tmp
        tmp*=x
        tmp%=p
        res%=p
    return res
def c_mul(c, f):
    n = len(f)
    for i in range(n):
        f[i]*=c
        f[i]%=p
    return f
def poly_add(f, g):
    n = len(g)
    for i in range(n):
        f[i]+=g[i]
        f[i]%=p
    return f


p = int(input())
a = list(map(int, input().split()))
inv = [0]*p
P = [1]
for i in range(p):
    inv[i] = pow(i, p-2, p)
for i in range(p):
    b = [-i, 1]
    P = poly_product(b, P)
R = [0]*p
for i in range(p):
    b = [-i, 1]
    Q, _ = poly_divide(b, P)
    v = assign(Q, i)
    Q=c_mul(inv[v%p]*a[i], Q)
    R = poly_add(R, Q)
print(*R)

Submission status: Accepted

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