#943774 (PyPy3) No.2605 Pickup Parentheses

提出ソース

結果

問題	No.2605 Pickup Parentheses
ユーザー	Shirotsume
提出日時	2024-01-12 23:29:08
言語	PyPy3 (7.3.15)
結果	AC
実行時間	1,357 ms / 2,000 ms
コード長	13,174 bytes
コンパイル時間	380 ms
コンパイル使用メモリ	82,624 KB
実行使用メモリ	220,912 KB
最終ジャッジ日時	2024-09-30 06:33:08
合計ジャッジ時間	47,345 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	301 ms 123,392 KB
testcase_01	AC	309 ms 123,520 KB
testcase_02	AC	304 ms 124,480 KB
testcase_03	AC	348 ms 136,848 KB
testcase_04	AC	364 ms 137,240 KB
testcase_05	AC	361 ms 137,216 KB
testcase_06	AC	363 ms 137,248 KB
testcase_07	AC	360 ms 137,348 KB
testcase_08	AC	377 ms 137,344 KB
testcase_09	AC	353 ms 137,024 KB
testcase_10	AC	362 ms 137,216 KB
testcase_11	AC	354 ms 137,268 KB
testcase_12	AC	360 ms 136,900 KB
testcase_13	AC	360 ms 137,448 KB
testcase_14	AC	363 ms 137,400 KB
testcase_15	AC	364 ms 137,264 KB
testcase_16	AC	352 ms 137,092 KB
testcase_17	AC	359 ms 137,296 KB
testcase_18	AC	883 ms 172,212 KB
testcase_19	AC	629 ms 154,008 KB
testcase_20	AC	414 ms 139,676 KB
testcase_21	AC	395 ms 137,936 KB
testcase_22	AC	349 ms 137,564 KB
testcase_23	AC	950 ms 174,332 KB
testcase_24	AC	385 ms 138,776 KB
testcase_25	AC	1,140 ms 186,888 KB
testcase_26	AC	1,027 ms 186,212 KB
testcase_27	AC	787 ms 167,528 KB
testcase_28	AC	1,217 ms 190,696 KB
testcase_29	AC	516 ms 146,828 KB
testcase_30	AC	770 ms 161,388 KB
testcase_31	AC	738 ms 158,620 KB
testcase_32	AC	521 ms 146,416 KB
testcase_33	AC	1,161 ms 192,040 KB
testcase_34	AC	1,024 ms 185,708 KB
testcase_35	AC	803 ms 167,104 KB
testcase_36	AC	1,071 ms 179,724 KB
testcase_37	AC	1,039 ms 182,624 KB
testcase_38	AC	469 ms 148,272 KB
testcase_39	AC	390 ms 140,100 KB
testcase_40	AC	640 ms 162,756 KB
testcase_41	AC	617 ms 164,136 KB
testcase_42	AC	741 ms 170,116 KB
testcase_43	AC	420 ms 143,344 KB
testcase_44	AC	416 ms 144,344 KB
testcase_45	AC	341 ms 137,472 KB
testcase_46	AC	374 ms 140,008 KB
testcase_47	AC	320 ms 133,120 KB
testcase_48	AC	561 ms 156,640 KB
testcase_49	AC	813 ms 173,672 KB
testcase_50	AC	534 ms 151,296 KB
testcase_51	AC	692 ms 167,108 KB
testcase_52	AC	577 ms 156,204 KB
testcase_53	AC	707 ms 165,332 KB
testcase_54	AC	544 ms 151,632 KB
testcase_55	AC	657 ms 163,380 KB
testcase_56	AC	415 ms 141,872 KB
testcase_57	AC	722 ms 168,168 KB
testcase_58	AC	1,297 ms 220,912 KB
testcase_59	AC	837 ms 175,560 KB
testcase_60	AC	1,055 ms 187,300 KB
testcase_61	AC	1,029 ms 184,216 KB
testcase_62	AC	1,093 ms 189,204 KB
testcase_63	AC	1,068 ms 187,000 KB
testcase_64	AC	1,122 ms 193,176 KB
testcase_65	AC	1,105 ms 183,276 KB
testcase_66	AC	1,357 ms 211,168 KB
testcase_67	AC	1,045 ms 183,584 KB
testcase_68	AC	405 ms 141,908 KB
testcase_69	AC	314 ms 122,880 KB
testcase_70	AC	323 ms 130,048 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import sys, time, random
from collections import deque, Counter, defaultdict
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())
inf = 2 ** 63 - 1
mod = 998244353
class Calculator:
    def __init__(self):
        self.primitive=self.__primitive_root()
        self.__build_up()

    def __primitive_root(self):
        p=Mod
        if p==2:
            return 1
        if p==998244353:
            return 3
        if p==10**9+7:
            return 5
        if p==163577857:
            return 23
        if p==167772161:
            return 3
        if  p==469762049:
            return 3

        fac=[]
        q=2
        v=p-1

        while v>=q*q:
            e=0
            while v%q==0:
                e+=1
                v//=q

            if e>0:
                fac.append(q)
            q+=1

        if v>1:
            fac.append(v)

        g=2
        while g<p:
            if pow(g,p-1,p)!=1:
                return None

            flag=True
            for q in fac:
                if pow(g,(p-1)//q,p)==1:
                    flag=False
                    break

            if flag:
                return g

            g+=1

    #参考元: https://judge.yosupo.jp/submission/72676
    def __build_up(self):
        rank2=(~(Mod-1)&(Mod-2)).bit_length()
        root=[0]*(rank2+1); iroot=[0]*(rank2+1)
        rate2=[0]*max(0, rank2-1); irate2=[0]*max(0, rank2-1)
        rate3=[0]*max(0, rank2-2); irate3=[0]*max(0, rank2-2)

        root[-1]=pow(self.primitive, (Mod-1)>>rank2, Mod)
        iroot[-1]=pow(root[-1], Mod-2, Mod)

        for i in range(rank2)[::-1]:
            root[i]=root[i+1]*root[i+1]%Mod
            iroot[i]=iroot[i+1]*iroot[i+1]%Mod

        prod=iprod=1
        for i in range(rank2-1):
            rate2[i]=root[i+2]*prod%Mod
            irate2[i]=iroot[i+2]*prod%Mod
            prod*=iroot[i+2]; prod%=Mod
            iprod*=root[i+2]; iprod%=Mod

        prod=iprod = 1
        for i in range(rank2-2):
            rate3[i]=root[i + 3]*prod%Mod
            irate3[i]=iroot[i + 3]*iprod%Mod
            prod*=iroot[i + 3]; prod%=Mod
            iprod*=root[i + 3]; iprod%=Mod

        self.root=root; self.iroot=iroot
        self.rate2=rate2; self.irate2=irate2
        self.rate3=rate3; self.irate3=irate3

    def Add(self, A, B):
        """ 必要ならば末尾に元を追加して, [A[i]+B[i]] を求める.

        """
        if type(A)==int:
            A=[A]

        if type(B)==int:
            B=[B]

        m=min(len(A), len(B))
        C=[(A[i]+B[i])%Mod for i in range(m)]
        C.extend(A[m:])
        C.extend(B[m:])
        return C

    def Sub(self, A, B):
        """ 必要ならば末尾に元を追加して, [A[i]-B[i]] を求める.

        """
        if type(A)==int:
            A=[A]

        if type(B)==int:
            B=[B]

        m=min(len(A), len(B))
        C=[0]*m
        C=[(A[i]-B[i])%Mod for i in range(m)]
        C.extend(A[m:])
        C.extend([-b%Mod for b in B[m:]])
        return C

    def Times(self,A, k):
        """ [k*A[i]] を求める.

        """
        return [k*a%Mod for a in A]

    #参考元 https://judge.yosupo.jp/submission/72676
    def NTT(self, A):
        """ A に Mod を法とする数論変換を施す

        ※ Mod はグローバル変数から指定

        References:
        https://github.com/atcoder/ac-library/blob/master/atcoder/convolution.hpp
        https://judge.yosupo.jp/submission/72676
        """

        N=len(A)
        H=(N-1).bit_length()
        l=0

        I=self.root[2]
        rate2=self.rate2; rate3=self.rate3

        while l<H:
            if H-l==1:
                p=1<<(H-l-1)
                rot=1
                for s in range(1<<l):
                    offset=s<<(H-l)
                    for i in range(p):
                        x=A[i+offset]; y=A[i+offset+p]*rot%Mod
                        A[i+offset]=(x+y)%Mod
                        A[i+offset+p]=(x-y)%Mod

                    if s+1!=1<<l:
                        rot*=rate2[(~s&-~s).bit_length()-1]
                        rot%=Mod
                l+=1
            else:
                p=1<<(H-l-2)
                rot=1
                for s in range(1<<l):
                    rot2=rot*rot%Mod
                    rot3=rot2*rot%Mod
                    offset=s<<(H-l)
                    for i in range(p):
                        a0=A[i+offset]
                        a1=A[i+offset+p]*rot
                        a2=A[i+offset+2*p]*rot2
                        a3=A[i+offset+3*p]*rot3

                        alpha=(a1-a3)%Mod*I

                        A[i+offset]=(a0+a2+a1+a3)%Mod
                        A[i+offset+p]=(a0+a2-a1-a3)%Mod
                        A[i+offset+2*p]=(a0-a2+alpha)%Mod
                        A[i+offset+3*p]=(a0-a2-alpha)%Mod

                    if s+1!=1<<l:
                        rot*=rate3[(~s&-~s).bit_length()-1]
                        rot%=Mod
                l+=2

    #参考元 https://judge.yosupo.jp/submission/72676
    def Inverse_NTT(self, A):
        """ A を Mod を法とする逆数論変換を施す

        ※ Mod はグローバル変数から指定

        References:
        https://github.com/atcoder/ac-library/blob/master/atcoder/convolution.hpp
        https://judge.yosupo.jp/submission/72676
        """
        N=len(A)
        H=(N-1).bit_length()
        l=H

        J=self.iroot[2]
        irate2=self.rate2; irate3=self.irate3

        while l:
            if l==1:
                p=1<<(H-l)
                irot=1
                for s in range(1<<(l-1)):
                    offset=s<<(H-l+1)
                    for i in range(p):
                        x=A[i+offset]; y=A[i+offset+p]
                        A[i+offset]=(x+y)%Mod
                        A[i+offset+p]=(x-y)*irot%Mod

                    if s+1!=1<<(l-1):
                        irot*=irate2[(~s&-~s).bit_length()-1]
                        irot%=Mod
                l-=1
            else:
                p=1<<(H-l)
                irot=1
                for s in range(1<<(l-2)):
                    irot2=irot*irot%Mod
                    irot3=irot2*irot%Mod
                    offset=s<<(H-l+2)
                    for i in range(p):
                        a0=A[i+offset]
                        a1=A[i+offset+p]
                        a2=A[i+offset+2*p]
                        a3=A[i+offset+3*p]

                        beta=(a2-a3)*J%Mod

                        A[i+offset]=(a0+a1+a2+a3)%Mod
                        A[i+offset+p]=(a0-a1+beta)*irot%Mod
                        A[i+offset+2*p]=(a0+a1-a2-a3)*irot2%Mod
                        A[i+offset+3*p]=(a0-a1-beta)*irot3%Mod

                    if s+1!=1<<(l-2):
                        irot*=irate3[(~s&-~s).bit_length()-1]
                        irot%=Mod
                l-=2
        N_inv=pow(N,Mod-2,Mod)
        for i in range(N):
            A[i]=N_inv*A[i]%Mod

    def non_zero_count(self, A):
        """ A にある非零の数を求める. """
        return len(A)-A.count(0)

    def is_sparse(self, A, K=None):
        """ A が疎かどうかを判定する. """

        if K==None:
            K=25

        return self.non_zero_count(A)<=K

    def coefficients_list(self, A):
        """ A にある非零のリストを求める.


        output: ( [d[0], ..., d[k-1] ], [f[0], ..., f[k-1] ]) : a[d[j]]=f[j] であることを表している.
        """

        f=[]; d=[]
        for i in range(len(A)):
            if A[i]:
                d.append(i)
                f.append(A[i])
        return d,f

    def Convolution(self, A, B):
        """ A, B で Mod を法とする畳み込みを求める.

        ※ Mod はグローバル変数から指定
        """
        if not A or not B:
            return []

        N=len(A)
        M=len(B)
        L=M+N-1

        if min(N,M)<=50:
            if N<M:
                N,M=M,N
                A,B=B,A
            C=[0]*L
            for i in range(N):
                for j in range(M):
                    C[i+j]+=A[i]*B[j]
                    C[i+j]%=Mod
            return C

        H=L.bit_length()
        K=1<<H

        A=A+[0]*(K-N)
        B=B+[0]*(K-M)

        self.NTT(A)
        self.NTT(B)

        for i in range(K):
            A[i]=A[i]*B[i]%Mod

        self.Inverse_NTT(A)

        return A[:L]

    def Autocorrelation(self, A):
        """ A 自身に対して,Mod を法とする畳み込みを求める.

        ※ Mod はグローバル変数から指定
        """
        N=len(A)
        L=2*N-1

        if N<=50:
            C=[0]*L
            for i in range(N):
                for j in range(N):
                    C[i+j]+=A[i]*A[j]
                    C[i+j]%=Mod
            return C

        H=L.bit_length()
        K=1<<H

        A=A+[0]*(K-N)

        self.NTT(A)

        for i in range(K):
            A[i]=A[i]*A[i]%Mod
        self.Inverse_NTT(A)

        return A[:L]

    def Multiple_Convolution(self, *A):
        """ A=(A[0], A[1], ..., A[d-1]) で Mod を法とする畳み込みを行う.

        """

        from collections import deque

        if not A:
            return [1]

        Q=deque(list(range(len(A))))
        A=list(A)

        while len(Q)>=2:
            i=Q.popleft(); j=Q.popleft()
            A[i]=self.Convolution(A[i], A[j])
            Q.append(i)

        i=Q.popleft()
        return A[i]

    def Inverse(self, F, length=None):
        if length==None:
            M=len(F)
        else:
            M=length

        if M<=0:
            return []

        if self.is_sparse(F):
            """
            愚直に漸化式を用いて求める.
            計算量: F にある係数が非零の項の個数を K, 求める最大次数を N として, O(NK) 時間
            """
            d,f=self.coefficients_list(F)

            G=[0]*M
            alpha=pow(F[0], Mod-2, Mod)
            G[0]=alpha

            for i in range(1, M):
                for j in range(1, len(d)):
                    if d[j]<=i:
                        G[i]+=f[j]*G[i-d[j]]%Mod
                    else:
                        break

                G[i]%=Mod
                G[i]=(-alpha*G[i])%Mod
            del G[M:]
        else:
            """
            FFTの理論を応用して求める.
            計算量: 求めたい項の個数をNとして, O(N log N)

            Reference: https://judge.yosupo.jp/submission/42413
            """

            N=len(F)
            r=pow(F[0],Mod-2,Mod)

            m=1
            G=[r]
            while m<M:
                A=F[:min(N, 2*m)]; A+=[0]*(2*m-len(A))
                B=G.copy(); B+=[0]*(2*m-len(B))

                Calc.NTT(A); Calc.NTT(B)
                for i in range(2*m):
                    A[i]=A[i]*B[i]%Mod

                Calc.Inverse_NTT(A)
                A=A[m:]+[0]*m
                Calc.NTT(A)
                for i in range(2*m):
                    A[i]=-A[i]*B[i]%Mod
                Calc.Inverse_NTT(A)

                G.extend(A[:m])
                m<<=1
            G=G[:M]
        return G

    def Floor_Div(self, F, G):
        assert F[-1]
        assert G[-1]

        F_deg=len(F)-1
        G_deg=len(G)-1

        if F_deg<G_deg:
            return []

        m=F_deg-G_deg+1
        return self.Convolution(F[::-1], Calc.Inverse(G[::-1],m))[m-1::-1]

    def Mod(self, F, G):
        while F and F[-1]==0:
            F.pop()

        while G and G[-1]==0:
            G.pop()

        if not F:
            return []

        return Calc.Sub(F, Calc.Convolution(Calc.Floor_Div(F,G),G))
class Combinatorics():
    def __init__(self, mod, maxi):
        self.mod = mod
        self.maxi = maxi
        self.facs = [1] * (maxi + 1)
        self.factinvs = [1] * (maxi + 1)
        self.invs = [1] * (maxi + 1)
        for i in range(2, self.maxi + 1):
            self.facs[i] = ((self.facs[i-1] * i) % self.mod)
            self.invs[i] = (-self.invs[self.mod % i] * (self.mod // i)) % self.mod
            self.factinvs[i] = (self.factinvs[i-1] * self.invs[i]) % self.mod
            
    def choose(self, n, k):
        if k < 0 or k > n: return 0
        if k == 0 or k == n: return 1
        k = min(k, n - k)
        return (((self.facs[n] * self.factinvs[k]) % self.mod) * self.factinvs[n-k]) % self.mod
    
    def perm(self, n, k):
        return (self.choose(n, k) * self.facs[k]) % self.mod

    def homop(self, n, k):
        if n == k == 0:
            return 1
        return self.choose(n + k - 1, k)
Mod = mod
Calc = Calculator()
n, m = mi()
C = Combinatorics(mod, 25* 10 ** 5 + 2)
a = []

for _ in range(m):
    l, r = mi()
    a.append(r - l + 1)
A = []
cat = [0] * (2 * n + 3)
for i in range(1, n + 1):
    cat[2 * i] = C.choose(2 * i, i) * pow(i + 1, -1, mod) % mod
for v in a:
    now = [0] * (v + 1)
    now[0] = 1
    now[v] = -cat[v]
    A.append(now)
C = Calc.Multiple_Convolution(*A)
C += [0] * (n + 1 - len(C))
ans = 0
cat[0] = 1
for i in range(n + 1):
    ans += C[i] * cat[n - i] % mod
ans %= mod
print(ans)

yukicoder

結果

テストケース

ソースコード