結果

問題 No.1145 Sums of Powers
ユーザー やまぐちたいきやまぐちたいき
提出日時 2020-10-25 22:43:09
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 4,280 bytes
コンパイル時間 598 ms
コンパイル使用メモリ 11,368 KB
実行使用メモリ 43,448 KB
最終ジャッジ日時 2023-09-29 02:20:59
合計ジャッジ時間 7,018 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 146 ms
30,212 KB
testcase_01 AC 143 ms
30,192 KB
testcase_02 TLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

mod = 998244353

def convolve(f, g):
    fft_len = 1
    while 2 * fft_len < len(f) + len(g) - 1:
        fft_len *= 2
    fft_len *= 2
    Ff = np.fft.rfft(f, fft_len)
    Fg = np.fft.rfft(g, fft_len)
    Fh = Ff * Fg
    h = np.fft.irfft(Fh, fft_len)
    h = np.rint(h).astype(np.int64)
    return h[:len(f) + len(g) - 1]

def convolve2(f, g):
    f1, f2 = np.divmod(f, 1 << 15)
    g1, g2 = np.divmod(g, 1 << 15)
    a = convolve(f1, g1)%mod
    c = convolve(f2, g2)%mod
    b = (convolve(f1+f2, g1+g2)-(a+c))%mod
    h = (a << 30) + (b << 15) + c
    return h%mod

class poly(object):

    def __init__(self, coef):
        if isinstance(coef, int):
            coef = [coef]
        self.coef = np.array([c%mod for c in coef], dtype=np.int64)
        self.n = len(coef)

    def __getitem__(self, item):
        return poly(self.coef[item])

    def __setitem__(self, key, value):
        self.coef[key] = value%mod

    def __len__(self):
        return self.n

    def __add__(p, q):
        n = max(len(p),len(q))
        return poly((p.pad(n).coef+q.pad(n).coef)%mod)

    def __sub__(p, q):
        n = max(len(p),len(q))
        p.pad(n)
        q.pad(n)
        return poly((p.pad(n).coef-q.pad(n).coef)%mod)

    def __mul__(p, q):
        return poly(convolve2(p.coef,q.coef))

    def __truediv__(p, q):
        return p*q.inv()

    def pad(self, n):
        if len(self)<n:
            res = poly(np.pad(self.coef,[0,n-len(self)]))
            return res
        else:
            return self

    def inv(self, n=None):
        if n is None:
            n = len(self)
        res = poly([pow(int(self.coef[0]),mod-2,mod)])
        if len(self)==1:
            res.pad(n)
            return res
        while len(res) < n:
            p = res*self
            p.coef[0] -= 2
            p.coef *= -1
            res = (res*p)[:2*len(res)]
        return res[:n]

    def rev(self):
        n = len(self)
        res = [0]*n
        for i in range(n):
            if i%2==0:
                res[i] = self.coef[i]
            if i%2==1:
                res[i] = -self.coef[i]%mod
        return poly(res)

    def integral(self):
        n = len(self)
        res = poly([0]*(n+1))
        for i in range(n):
            res[i+1] = pow(i+1,mod-2,mod)*self.coef[i]%mod
        return res

    def differential(self):
        n = len(self)
        res = poly([0]*n)
        for i in range(n-1):
            res[i] = (i+1)*self.coef[i+1]%mod
        return res

    def log(self, n=None):
        p = self.differential()
        q = self.inv(n)
        res = (p*q).integral()
        if n is None:
            n = len(self)
        return res[:n]

    def exp(self, n=None):
        if n is None:
            n = len(self)
        res = poly(1)
        while len(res) < n:
            p = self-res.log(2*len(res))
            p.coef[0] += 1
            res = (res*p)[:2*len(res)]
        return res[:n]

    def pow(self, k, n=None):
        if n is None:
            n = k*(len(self)-1)+1
        return (self.log(n)*poly(k)).exp(n)
        
def get_dev_coef(P,Q,n):
    if Q[0] != 1:
        r = pow(int(Q[0]), mod-2, mod)
        R = poly(r)
        P *= R
        Q *= R
    if n==0:
        return P[0]
    Qr = Q.rev()
    q = poly((Q*Qr)[::2])
    if n%2==0:
        p = poly((P*Qr)[::2])
    else:
        p = poly((P*Qr)[1::2])
    return get_dev_coef(p,q,n//2)


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

# 多項式の積をsegtreeで持つ
N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [poly(1)]*(4*N0) #長さが足りないことがある. 3*N0にすればいい?

# k番目の要素をxに更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = data[2*k+1]*data[2*k+2]

# [l,r)の積
def query(l, r):
    L = l + N0; R = r + N0
    s = poly(1)
    while L < R:
        if R & 1:
            R -= 1
            s = s*data[R-1]

        if L & 1:
            s = s*data[L-1]
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(N):
    update(i, poly([1,-A[i]]))

poly_ans = poly(-1)*query(0,N).log(M+1)

ans = []
for i in range(M):
    ans.append((i+1)*poly_ans.coef[i+1]%mod)

print(*ans)
0