#929482 (PyPy3) No.1388 Less than K

提出ソース

結果

問題	No.1388 Less than K
ユーザー	vwxyz
提出日時	2023-11-19 01:29:07
言語	PyPy3 (7.3.15)
結果	MLE
実行時間	-
コード長	4,365 bytes
コンパイル時間	542 ms
コンパイル使用メモリ	82,224 KB
実行使用メモリ	849,248 KB
最終ジャッジ日時	2024-09-26 06:01:06
合計ジャッジ時間	27,354 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	171 ms 89,588 KB
testcase_01	AC	168 ms 89,472 KB
testcase_02	AC	189 ms 90,376 KB
testcase_03	AC	167 ms 89,428 KB
testcase_04	AC	183 ms 90,084 KB
testcase_05	AC	233 ms 96,764 KB
testcase_06	AC	212 ms 90,624 KB
testcase_07	AC	175 ms 89,592 KB
testcase_08	AC	274 ms 101,580 KB
testcase_09	AC	201 ms 90,624 KB
testcase_10	AC	207 ms 90,624 KB
testcase_11	AC	192 ms 90,260 KB
testcase_12	AC	251 ms 100,204 KB
testcase_13	AC	290 ms 107,936 KB
testcase_14	AC	336 ms 117,356 KB
testcase_15	AC	551 ms 153,668 KB
testcase_16	AC	708 ms 195,328 KB
testcase_17	AC	986 ms 254,752 KB
testcase_18	AC	1,592 ms 367,064 KB
testcase_19	AC	2,248 ms 493,528 KB
testcase_20	MLE	-
testcase_21	AC	322 ms 127,232 KB
testcase_22	AC	220 ms 111,872 KB
testcase_23	AC	233 ms 105,600 KB
testcase_24	AC	266 ms 112,384 KB
testcase_25	AC	308 ms 117,376 KB
testcase_26	AC	260 ms 115,072 KB
testcase_27	AC	242 ms 110,080 KB
testcase_28	AC	208 ms 104,960 KB
testcase_29	AC	209 ms 104,992 KB
testcase_30	AC	185 ms 90,240 KB
testcase_31	AC	191 ms 93,440 KB
testcase_32	AC	169 ms 89,856 KB
testcase_33	AC	226 ms 115,200 KB
testcase_34	AC	225 ms 114,816 KB
testcase_35	AC	223 ms 112,128 KB
testcase_36	AC	250 ms 114,944 KB
testcase_37	AC	234 ms 118,400 KB
testcase_38	AC	365 ms 133,060 KB
testcase_39	AC	285 ms 123,608 KB
testcase_40	AC	326 ms 124,464 KB
testcase_41	AC	575 ms 187,964 KB
testcase_42	AC	276 ms 126,336 KB
testcase_43	AC	2,471 ms 129,024 KB
testcase_44	MLE	-
testcase_45	MLE	-
testcase_46	--	-
testcase_47	--	-
testcase_48	--	-
testcase_49	--	-
testcase_50	--	-
testcase_51	--	-
testcase_52	--	-
testcase_53	--	-
testcase_54	--	-
testcase_55	--	-
testcase_56	--	-
testcase_57	--	-
testcase_58	--	-
testcase_59	--	-
testcase_60	--	-
testcase_61	--	-
testcase_62	--	-
testcase_63	--	-
testcase_64	--	-
testcase_65	--	-
testcase_66	--	-
testcase_67	--	-
testcase_68	--	-
testcase_69	--	-
testcase_70	--	-
testcase_71	--	-
testcase_72	--	-
testcase_73	--	-
testcase_74	--	-
testcase_75	--	-
testcase_76	--	-

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

ソースコード

raw source code

import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
import time
from collections import Counter,deque,defaultdict
from functools import lru_cache,reduce
from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max
def _heappush_max(heap,item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappushpop_max(heap, item):
    if heap and item < heap[0]:
        item, heap[0] = heap[0], item
        heapq._siftup_max(heap, 0)
    return item
from math import gcd as GCD
read=sys.stdin.read
readline=sys.stdin.readline
readlines=sys.stdin.readlines
write=sys.stdout.write
#import pypyjit
#pypyjit.set_param('max_unroll_recursion=-1')
#sys.set_int_max_str_digits(10**9)

def Extended_Euclid(n,m):
    stack=[]
    while m:
        stack.append((n,m))
        n,m=m,n%m
    if n>=0:
        x,y=1,0
    else:
        x,y=-1,0
    for i in range(len(stack)-1,-1,-1):
        n,m=stack[i]
        x,y=y,x-(n//m)*y
    return x,y

class MOD:
    def __init__(self,p,e=None):
        self.p=p
        self.e=e
        if self.e==None:
            self.mod=self.p
        else:
            self.mod=self.p**self.e

    def Pow(self,a,n):
        a%=self.mod
        if n>=0:
            return pow(a,n,self.mod)
        else:
            #assert math.gcd(a,self.mod)==1
            x=Extended_Euclid(a,self.mod)[0]
            return pow(x,-n,self.mod)

    def Build_Fact(self,N):
        assert N>=0
        self.factorial=[1]
        if self.e==None:
            for i in range(1,N+1):
                self.factorial.append(self.factorial[-1]*i%self.mod)
        else:
            self.cnt=[0]*(N+1)
            for i in range(1,N+1):
                self.cnt[i]=self.cnt[i-1]
                ii=i
                while ii%self.p==0:
                    ii//=self.p
                    self.cnt[i]+=1
                self.factorial.append(self.factorial[-1]*ii%self.mod)
        self.factorial_inve=[None]*(N+1)
        self.factorial_inve[-1]=self.Pow(self.factorial[-1],-1)
        for i in range(N-1,-1,-1):
            ii=i+1
            while ii%self.p==0:
                ii//=self.p
            self.factorial_inve[i]=(self.factorial_inve[i+1]*ii)%self.mod

    def Build_Inverse(self,N):
        self.inverse=[None]*(N+1)
        assert self.p>N
        self.inverse[1]=1
        for n in range(2,N+1):
            if n%self.p==0:
                continue
            a,b=divmod(self.mod,n)
            self.inverse[n]=(-a*self.inverse[b])%self.mod
    
    def Inverse(self,n):
        return self.inverse[n]

    def Fact(self,N):
        if N<0:
            return 0
        retu=self.factorial[N]
        if self.e!=None and self.cnt[N]:
            retu*=pow(self.p,self.cnt[N],self.mod)%self.mod
            retu%=self.mod
        return retu

    def Fact_Inve(self,N):
        if self.e!=None and self.cnt[N]:
            return None
        return self.factorial_inve[N]

    def Comb(self,N,K,divisible_count=False):
        if K<0 or K>N:
            return 0
        retu=self.factorial[N]*self.factorial_inve[K]%self.mod*self.factorial_inve[N-K]%self.mod
        if self.e!=None:
            cnt=self.cnt[N]-self.cnt[N-K]-self.cnt[K]
            if divisible_count:
                return retu,cnt
            else:
                retu*=pow(self.p,cnt,self.mod)
                retu%=self.mod
        return retu

H,W,K=map(int,readline().split())
H-=1;W-=1
K//=2
mod=998244353
MD=MOD(mod)
MD.Build_Fact(H+W)
N=min(H,W)
ans=0
if K<=400:
    dp=[[0]*(2*K+1) for h in range(N+1)]
    dp[0][K]=1
    for h in range(N+1):
        for w in range(max(h-K,0),min(h+K,N)+1):
            if h and abs((h-1)-w)<=K:
                dp[h][w-h+K]+=dp[h-1][w-(h-1)+K]
            if w and abs(h-(w-1))<=K:
                dp[h][w-h+K]+=dp[h][(w-1)-h+K]
            dp[h][w-h+K]%=mod
    for cnt in range(N+1):
        ans+=MD.Fact(H+W)*MD.Fact_Inve(H-cnt)%mod*MD.Fact_Inve(W-cnt)%mod*MD.Fact_Inve(2*cnt)%mod*dp[cnt][K]%mod
        ans%=mod
else:
    for cnt in range(N+1):
        s=MD.Comb(2*cnt,cnt)
        for i in range(1,cnt//(K+1)+1):
            s+=2*MD.Comb(2*cnt,cnt-(K+1)*i)*(-1)**i
            s%=mod
        ans+=MD.Fact(H+W)*MD.Fact_Inve(H-cnt)%mod*MD.Fact_Inve(W-cnt)%mod*MD.Fact_Inve(2*cnt)%mod*s%mod
        ans%=mod
print(ans)

yukicoder

結果

テストケース

ソースコード