結果

問題 No.1145 Sums of Powers
ユーザー やまぐちたいきやまぐちたいき
提出日時 2020-10-25 23:13:34
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 3,792 bytes
コンパイル時間 146 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 69,304 KB
最終ジャッジ日時 2024-07-21 21:09:08
合計ジャッジ時間 6,633 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 525 ms
50,124 KB
testcase_01 AC 572 ms
44,428 KB
testcase_02 AC 689 ms
44,304 KB
testcase_03 TLE -
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)


from collections import deque
N,M = map(int,input().split())
A = list(map(int,input().split()))
q = deque([poly([1,-A[i]]) for i in range(N)])

while len(q)>1:
    p1 = q.popleft()
    p2 = q.popleft()
    p = p1*p2
    q.append(p)

poly_ans = poly(-1)*q[0].log(M+1)

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

print(*ans)
0