#862157 (PyPy3) No.1145 Sums of Powers

提出ソース
結果

問題	No.1145 Sums of Powers
ユーザー	vwxyz
提出日時	2023-04-22 18:27:38
言語	PyPy3 (7.3.15)
結果	AC
実行時間	1,773 ms / 2,000 ms
コード長	18,871 bytes
コンパイル時間	189 ms
コンパイル使用メモリ	82,816 KB
実行使用メモリ	188,740 KB
最終ジャッジ日時	2024-04-24 21:25:07
合計ジャッジ時間	6,585 ms
ジャッジサーバーID （参考情報）	judge4 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	58 ms 58,112 KB
testcase_01	AC	57 ms 58,368 KB
testcase_02	AC	161 ms 78,212 KB
testcase_03	AC	1,767 ms 188,740 KB
testcase_04	AC	1,773 ms 188,020 KB
testcase_05	AC	1,762 ms 187,272 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
import sys
from collections import deque
readline=sys.stdin.readline

def NTT(polynomial0,polynomial1):
    if len(polynomial0)*len(polynomial1)<=60:
        poly=[0]*(len(polynomial0)+len(polynomial1)-1)
        for i in range(len(polynomial0)):
            for j in range(len(polynomial1)):
                poly[i+j]+=polynomial0[i]*polynomial1[j]%mod
                poly[i+j]%=mod
        return poly
    if mod==998244353:
        prim_root=3
        prim_root_inve=332748118
    else:
        prim_root=Primitive_Root(mod)
        prim_root_inve=MOD(mod).Pow(prim_root,-1)
    def DFT(polynomial,n,inverse=False):
        if inverse:
            for bit in range(1,n+1):
                a=1<<bit-1
                x=pow(prim_root,mod-1>>bit,mod)
                U=[1]
                for _ in range(a):
                    U.append(U[-1]*x%mod)
                for i in range(1<<n-bit):
                    for j in range(a):
                        s=i*2*a+j
                        t=s+a
                        polynomial[s],polynomial[t]=(polynomial[s]+polynomial[t]*U[j])%mod,(polynomial[s]-polynomial[t]*U[j])%mod
            x=pow((mod+1)//2,n,mod)
            for i in range(1<<n):
                polynomial[i]*=x
                polynomial[i]%=mod
        else:
            for bit in range(n,0,-1):
                a=1<<bit-1
                x=pow(prim_root_inve,mod-1>>bit,mod)
                U=[1]
                for _ in range(a):
                    U.append(U[-1]*x%mod)
                for i in range(1<<n-bit):
                    for j in range(a):
                        s=i*2*a+j
                        t=s+a
                        polynomial[s],polynomial[t]=(polynomial[s]+polynomial[t])%mod,U[j]*(polynomial[s]-polynomial[t])%mod

    l=len(polynomial0)+len(polynomial1)-1
    n=(len(polynomial0)+len(polynomial1)-2).bit_length()
    polynomial0=polynomial0+[0]*((1<<n)-len(polynomial0))
    polynomial1=polynomial1+[0]*((1<<n)-len(polynomial1))
    DFT(polynomial0,n)
    DFT(polynomial1,n)
    ntt=[x*y%mod for x,y in zip(polynomial0,polynomial1)]
    DFT(ntt,n,inverse=True)
    ntt=ntt[:l]
    return ntt

class Polynomial:
    def __init__(self,polynomial,max_degree=-1,eps=0,mod=0):
        self.max_degree=max_degree
        if self.max_degree!=-1 and len(polynomial)>self.max_degree+1:
            self.polynomial=polynomial[:self.max_degree+1]
        else:
            self.polynomial=polynomial
        mod=mod
        self.eps=eps

    def __eq__(self,other):
        if type(other)!=Polynomial:
            return False
        if len(self.polynomial)!=len(other.polynomial):
            return False
        for i in range(len(self.polynomial)):
            if self.eps<abs(self.polynomial[i]-other.polynomial[i]):
                return False
        return True

    def __ne__(self,other):
        if type(other)!=Polynomial:
            return True
        if len(self.polynomial)!=len(other.polynomial):
            return True
        for i in range(len(self.polynomial)):
            if self.eps<abs(self.polynomial[i]-other.polynomial[i]):
                return True
        return False

    def __add__(self,other):
        if type(other)==Polynomial:
            summ=[0]*max(len(self.polynomial),len(other.polynomial))
            for i in range(len(self.polynomial)):
                summ[i]+=self.polynomial[i]
            for i in range(len(other.polynomial)):
                summ[i]+=other.polynomial[i]
            if mod:
                for i in range(len(summ)):
                    summ[i]%=mod
        else:
            summ=[x for x in self.polynomial] if self.polynomial else [0]
            summ[0]+=other
            if mod:
                summ[0]%=mod
        while summ and abs(summ[-1])<=self.eps:
            summ.pop()
        summ=Polynomial(summ,max_degree=self.max_degree,eps=self.eps,mod=mod)
        return summ

    def __sub__(self,other):
        if type(other)==Polynomial:
            diff=[0]*max(len(self.polynomial),len(other.polynomial))
            for i in range(len(self.polynomial)):
                diff[i]+=self.polynomial[i]
            for i in range(len(other.polynomial)):
                diff[i]-=other.polynomial[i]
            if mod:
                for i in range(len(diff)):
                    diff[i]%=mod
        else:
            diff=[x for x in self.polynomial] if self.polynomial else [0]
            diff[0]-=other
            if mod:
                diff[0]%=mod
        while diff and abs(diff[-1])<=self.eps:
            diff.pop()
        diff=Polynomial(diff,max_degree=self.max_degree,eps=self.eps,mod=mod)
        return diff

    def __mul__(self,other):
        if type(other)==Polynomial:
            if self.max_degree==-1:
                prod=[0]*(len(self.polynomial)+len(other.polynomial)-1)
                for i in range(len(self.polynomial)):
                    for j in range(len(other.polynomial)):
                        prod[i+j]+=self.polynomial[i]*other.polynomial[j]
            else:
                prod=[0]*min(len(self.polynomial)+len(other.polynomial)-1,self.max_degree+1)
                for i in range(len(self.polynomial)):
                    for j in range(min(len(other.polynomial),self.max_degree+1-i)):
                        prod[i+j]+=self.polynomial[i]*other.polynomial[j]
            if mod:
                for i in range(len(prod)):
                    prod[i]%=mod
        else:
            if mod:
                prod=[x*other%mod for x in self.polynomial]
            else:
                prod=[x*other for x in self.polynomial]
        while prod and abs(prod[-1])<=self.eps:
            prod.pop()
        prod=Polynomial(prod,max_degree=self.max_degree,eps=self.eps,mod=mod)
        return prod

    def __matmul__(self,other):
        assert type(other)==Polynomial
        if mod:
            prod=NTT(self.polynomial,other.polynomial)
        else:
            prod=FFT(self.polynomial,other.polynomial)
        if self.max_degree!=-1 and len(prod)>self.max_degree+1:
            prod=prod[:self.max_degree+1]
            while prod and abs(prod[-1])<=self.eps:
                prod.pop()
        prod=Polynomial(prod,max_degree=self.max_degree,eps=self.eps,mod=mod)
        return prod

    def __truediv__(self,other):
        if type(other)==Polynomial:
            assert other.polynomial
            for n in range(len(other.polynomial)):
                if self.eps<abs(other.polynomial[n]):
                    break
            assert len(self.polynomial)>n
            for i in range(n):
                assert abs(self.polynomial[i])<=self.eps
            self_polynomial=self.polynomial[n:]
            other_polynomial=other.polynomial[n:]
            if mod:
                inve=MOD(mod).Pow(other_polynomial[0],-1)
            else:
                inve=1/other_polynomial[0]
            quot=[]
            for i in range(len(self_polynomial)-len(other_polynomial)+1):
                if mod:
                    quot.append(self_polynomial[i]*inve%mod)
                else:
                    quot.append(self_polynomial[i]*inve)
                for j in range(len(other_polynomial)):
                    self_polynomial[i+j]-=other_polynomial[j]*quot[-1]
                    if mod:
                        self_polynomial[i+j]%=mod
            for i in range(max(0,len(self_polynomial)-len(other_polynomial)+1),len(self_polynomial)):
                if self.eps<abs(self_polynomial[i]):
                    assert self.max_degree!=-1
                    self_polynomial=self_polynomial[-len(other_polynomial)+1:]+[0]*(len(other_polynomial)-1-len(self_polynomial))
                    while len(quot)<=self.max_degree:
                        self_polynomial.append(0)
                        if mod:
                            quot.append(self_polynomial[0]*inve%mod)
                            self_polynomial=[(self_polynomial[i]-other_polynomial[i]*quot[-1])%mod for i in range(1,len(self_polynomial))]
                        else:
                            quot.append(self_polynomial[0]*inve)
                            self_polynomial=[(self_polynomial[i]-other_polynomial[i]*quot[-1]) for i in range(1,len(self_polynomial))]
                    break
            quot=Polynomial(quot,max_degree=self.max_degree,eps=self.eps,mod=mod)
        else:
            assert self.eps<abs(other)
            if mod:
                inve=MOD(mod).Pow(other,-1)
                quot=Polynomial([x*inve%mod for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=mod)
            else:
                quot=Polynomial([x/other for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=mod)
        return quot

    def __rtruediv__(self,other):
        assert self.polynomial and self.eps<self.polynomial[0]
        assert self.max_degree!=-1
        if mod:
            quot=[pow(self.polynomial[0],mod-2,mod)]
            if mod==998244353:
                prim_root=3
                prim_root_inve=332748118
            else:
                prim_root=Primitive_Root(mod)
                prim_root_inve=MOD(mod).Pow(prim_root,-1)
            def DFT(polynomial,n,inverse=False):
                polynomial=polynomial+[0]*((1<<n)-len(polynomial))
                if inverse:
                    for bit in range(1,n+1):
                        a=1<<bit-1
                        x=pow(prim_root,mod-1>>bit,mod)
                        U=[1]
                        for _ in range(a):
                            U.append(U[-1]*x%mod)
                        for i in range(1<<n-bit):
                            for j in range(a):
                                s=i*2*a+j
                                t=s+a
                                polynomial[s],polynomial[t]=(polynomial[s]+polynomial[t]*U[j])%mod,(polynomial[s]-polynomial[t]*U[j])%mod
                    x=pow((mod+1)//2,n,mod)
                    for i in range(1<<n):
                        polynomial[i]*=x
                        polynomial[i]%=mod
                else:
                    for bit in range(n,0,-1):
                        a=1<<bit-1
                        x=pow(prim_root_inve,mod-1>>bit,mod)
                        U=[1]
                        for _ in range(a):
                            U.append(U[-1]*x%mod)
                        for i in range(1<<n-bit):
                            for j in range(a):
                                s=i*2*a+j
                                t=s+a
                                polynomial[s],polynomial[t]=(polynomial[s]+polynomial[t])%mod,U[j]*(polynomial[s]-polynomial[t])%mod
                return polynomial
        else:
            quot=[1/self.polynomial[0]]
            def DFT(polynomial,n,inverse=False):
                N=len(polynomial)
                if inverse:
                    primitive_root=[math.cos(-i*2*math.pi/(1<<n))+math.sin(-i*2*math.pi/(1<<n))*1j for i in range(1<<n)]
                else:
                    primitive_root=[math.cos(i*2*math.pi/(1<<n))+math.sin(i*2*math.pi/(1<<n))*1j for i in range(1<<n)]
                polynomial=polynomial+[0]*((1<<n)-N)
                if inverse:
                    for bit in range(1,n+1):
                        a=1<<bit-1
                        for i in range(1<<n-bit):
                            for j in range(a):
                                s=i*2*a+j
                                t=s+a
                                polynomial[s],polynomial[t]=polynomial[s]+polynomial[t]*primitive_root[j<<n-bit],polynomial[s]-polynomial[t]*primitive_root[j<<n-bit]
                    for i in range(1<<n):
                        polynomial[i]=round((polynomial[i]/(1<<n)).real)
                else:
                    for bit in range(n,0,-1):
                        a=1<<bit-1
                        for i in range(1<<n-bit):
                            for j in range(a):
                                s=i*2*a+j
                                t=s+a
                                polynomial[s],polynomial[t]=polynomial[s]+polynomial[t],primitive_root[j<<n-bit]*(polynomial[s]-polynomial[t])

                return polynomial
        for n in range(self.max_degree.bit_length()):
            prev=quot
            if mod:
                quot=DFT([x*y%mod*y%mod for x,y in zip(DFT(self.polynomial[:1<<n+1],n+2),DFT(prev,n+2))],n+2,inverse=True)[:1<<n+1]
            else:
                polynomial=[x*y*y for x,y in zip(DFT(self.polynomial[:1<<n+1],n+2),DFT(prev,n+2))]
                quot=DFT(polynomial,n+2,inverse=True)[:1<<n+1]
            for i in range(1<<n):
                quot[i]=2*prev[i]-quot[i]
                if mod:
                    quot[i]%=mod
            for i in range(1<<n,1<<n+1):
                quot[i]=-quot[i]
                if mod:
                    quot[i]%=mod
        quot=quot[:self.max_degree+1]
        quot=Polynomial(quot,max_degree=self.max_degree,eps=self.eps,mod=mod)
        return quot

    def __floordiv__(self,other):
        assert type(other)==Polynomial
        quot=[0]*(len(self.polynomial)-len(other.polynomial)+1)
        rema=[x for x in self.polynomial]
        if mod:
            inve=MOD(mod).Pow(other.polynomial[-1],-1)
            for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):
                quot[i]=rema[i+len(other.polynomial)-1]*inve%mod
                for j in range(len(other.polynomial)):
                    rema[i+j]-=quot[i]*other.polynomial[j]
                    rema[i+j]%=mod
        else:
            inve=1/other.polynomial[-1]
            for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):
                quot[i]=rema[i+len(other.polynomial)-1]*inve
                for j in range(len(other.polynomial)):
                    rema[i+j]-=quot[i]*other.polynomial[j]
        quot=Polynomial(quot,max_degree=self.max_degree,eps=self.eps,mod=mod)
        return quot

    def __mod__(self,other):
        assert type(other)==Polynomial
        quot=[0]*(len(self.polynomial)-len(other.polynomial)+1)
        rema=[x for x in self.polynomial]
        if mod:
            inve=MOD(mod).Pow(other.polynomial[-1],-1)
            for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):
                quot[i]=rema[i+len(other.polynomial)-1]*inve%mod
                for j in range(len(other.polynomial)):
                    rema[i+j]-=quot[i]*other.polynomial[j]
                    rema[i+j]%=mod
        else:
            inve=1/other.polynomial[-1]
            for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):
                quot[i]=rema[i+len(other.polynomial)-1]*inve
                for j in range(len(other.polynomial)):
                    rema[i+j]-=quot[i]*other.polynomial[j]
        while rema and abs(rema[-1])<=self.eps:
            rema.pop()
        rema=Polynomial(rema,max_degree=self.max_degree,eps=self.eps,mod=mod)
        return rema

    def __divmod__(self,other):
        assert type(other)==Polynomial
        quot=[0]*(len(self.polynomial)-len(other.polynomial)+1)
        rema=[x for x in self.polynomial]
        if mod:
            inve=MOD(mod).Pow(other.polynomial[-1],-1)
            for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):
                quot[i]=rema[i+len(other.polynomial)-1]*inve%mod
                for j in range(len(other.polynomial)):
                    rema[i+j]-=quot[i]*other.polynomial[j]
                    rema[i+j]%=mod
        else:
            inve=1/other.polynomial[-1]
            for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):
                quot[i]=rema[i+len(other.polynomial)-1]*inve
                for j in range(len(other.polynomial)):
                    rema[i+j]-=quot[i]*other.polynomial[j]
        while rema and abs(rema[-1])<=self.eps:
            rema.pop()
        quot=Polynomial(quot,max_degree=self.max_degree,eps=self.eps,mod=mod)
        rema=Polynomial(rema,max_degree=self.max_degree,eps=self.eps,mod=mod)
        return quot,rema

    def __neg__(self):
        if mod:
            nega=Polynomial([(-x)%mod for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=mod)
        else:
            nega=Polynomial([-x for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=mod)
        return nega

    def __pos__(self):
        posi=Polynomial([x for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=mod)
        return posi

    def __bool__(self):
        return self.polynomial

    def __getitem__(self,n):
        if type(n)==int:
            if n<=len(self.polynomial)-1:
                return self.polynomial[n]
            else:
                return 0
        else:
            return Polynomial(polynomial=self.polynomial[n],max_degree=self.max_degree,eps=self.eps,mod=mod)
    
    def __setitem__(self,n,a):
        if mod:
            a%=mod
        if self.max_degree==-1 or n<=self.max_degree:
            if n<=len(self.polynomial)-1:
                self.polynomial[n]=a
            elif self.eps<abs(a):
                self.polynomial+=[0]*(n-len(self.polynomial))+[a]

    def __iter__(self):
        for x in self.polynomial:
            yield x

    def __call__(self,x):
        retu=0
        pow_x=1
        for i in range(len(self.polynomial)):
            retu+=pow_x*self.polynomial[i]
            pow_x*=x
            if mod:
                retu%=mod
                pow_x%=mod
        return retu

    def __str__(self):
        return "["+", ".join(map(str,self.polynomial))+"]"

    def differential(self):
        if mod:
            differential=[x*i%mod for i,x in enumerate(self.polynomial[1:],1)]
        else:
            differential=[x*i for i,x in enumerate(self.polynomial[1:],1)]
        return Polynomial(differential,max_degree=self.max_degree,eps=self.eps,mod=mod)

    def integral(self):
        if mod:
            integral=[0]+[x*pow(i+1,mod-2,mod)%mod for i,x in enumerate(self.polynomial)]
        else:
            integral=[0]+[x/(i+1) for i,x in enumerate(self.polynomial)]
        while integral and abs(integral[-1])<=self.eps:
            integral.pop()
        return Polynomial(integral,max_degree=self.max_degree,eps=self.eps,mod=mod)

    def log(self):
        assert self.max_degree!=-1
        assert self.polynomial and abs(self.polynomial[0]-1)<=self.eps
        log=(self.differential()@(1/self)).integral()
        return log

    def Degree(self):
        return len(self.polynomial)-1

N,M=map(int,readline().split())
A=list(map(int,readline().split()))
mod=998244353
queue=deque([[1,-a] for a in A])
while len(queue)>=2:
    f0=queue.pop()
    f1=queue.pop()
    f=NTT(f0,f1)[:M+1]
    queue.appendleft(f)

ans=0
f=Polynomial(queue[0],max_degree=M,mod=mod)
f=-(f.log())
ans_lst=[f[i]*i%mod for i in range(1,M+1)]
print(*ans_lst)
yukicoder

結果

テストケース

ソースコード
