結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 508 ms
52,052 KB
testcase_01 AC 491 ms
44,336 KB
testcase_02 AC 1,093 ms
44,328 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)


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

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [poly(1)] * (n + 1)

    def prod_tot(self, i):
        s = poly(1)
        i += 1
        while i > 0:
            s *= self.tree[i]
            i -= i & -i
        return s

    def prod(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] *= x
            i += i & -i
bit = BIT(N)
for i in range(N):
    bit.prod(i, poly([1,-A[i]]))

poly_ans = poly(-1)*bit.prod_tot(N-1).log(M+1)

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

print(*ans)
0