#929491 (PyPy3) No.1388 Less than K

提出ソース

結果

問題	No.1388 Less than K
ユーザー	vwxyz
提出日時	2023-11-19 01:52:43
言語	PyPy3 (7.3.15)
結果	TLE
実行時間	-
コード長	4,460 bytes
コンパイル時間	536 ms
コンパイル使用メモリ	82,048 KB
実行使用メモリ	134,016 KB
最終ジャッジ日時	2024-09-26 06:05:16
合計ジャッジ時間	27,249 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	127 ms 95,104 KB
testcase_01	AC	133 ms 89,600 KB
testcase_02	AC	143 ms 90,368 KB
testcase_03	AC	126 ms 89,460 KB
testcase_04	AC	142 ms 90,496 KB
testcase_05	AC	165 ms 90,924 KB
testcase_06	AC	157 ms 90,496 KB
testcase_07	AC	128 ms 89,600 KB
testcase_08	AC	180 ms 91,776 KB
testcase_09	AC	151 ms 90,496 KB
testcase_10	AC	147 ms 90,588 KB
testcase_11	AC	147 ms 90,368 KB
testcase_12	AC	176 ms 92,288 KB
testcase_13	AC	198 ms 93,440 KB
testcase_14	AC	222 ms 94,336 KB
testcase_15	AC	374 ms 97,664 KB
testcase_16	AC	472 ms 100,736 KB
testcase_17	AC	652 ms 103,936 KB
testcase_18	AC	1,009 ms 111,616 KB
testcase_19	AC	1,383 ms 117,632 KB
testcase_20	AC	1,448 ms 118,144 KB
testcase_21	AC	216 ms 117,760 KB
testcase_22	AC	176 ms 112,256 KB
testcase_23	AC	167 ms 99,328 KB
testcase_24	AC	195 ms 105,344 KB
testcase_25	AC	206 ms 107,648 KB
testcase_26	AC	202 ms 109,696 KB
testcase_27	AC	177 ms 103,852 KB
testcase_28	AC	164 ms 104,960 KB
testcase_29	AC	169 ms 105,236 KB
testcase_30	AC	140 ms 90,240 KB
testcase_31	AC	146 ms 93,720 KB
testcase_32	AC	132 ms 89,728 KB
testcase_33	AC	177 ms 115,068 KB
testcase_34	AC	174 ms 114,944 KB
testcase_35	AC	180 ms 112,000 KB
testcase_36	AC	212 ms 114,944 KB
testcase_37	AC	191 ms 118,144 KB
testcase_38	AC	261 ms 118,400 KB
testcase_39	AC	211 ms 114,688 KB
testcase_40	AC	235 ms 112,304 KB
testcase_41	AC	348 ms 128,896 KB
testcase_42	AC	203 ms 118,272 KB
testcase_43	AC	1,223 ms 129,024 KB
testcase_44	AC	2,202 ms 128,384 KB
testcase_45	TLE	-
testcase_46	TLE	-
testcase_47	AC	2,774 ms 125,304 KB
testcase_48	AC	2,375 ms 129,332 KB
testcase_49	TLE	-
testcase_50	AC	2,810 ms 128,768 KB
testcase_51	TLE	-
testcase_52	TLE	-
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<=500:
    for h in range(N+1):
        if h:
            prev=dp
            dp=[0]*(2*K+1)
        else:
            dp=[0]*(2*K+1)
            dp[K]=1
        for w in range(max(h-K,0),min(h+K,N)+1):
            if h and abs((h-1)-w)<=K:
                dp[w-h+K]+=prev[w-(h-1)+K]
            if w and abs(h-(w-1))<=K:
                dp[w-h+K]+=dp[(w-1)-h+K]
            dp[w-h+K]%=mod
        ans+=MD.Fact(H+W)*MD.Fact_Inve(H-h)%mod*MD.Fact_Inve(W-h)%mod*MD.Fact_Inve(2*h)%mod*dp[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):
            if i%2:
                s-=2*MD.Comb(2*cnt,cnt-(K+1)*i)
            else:
                s+=2*MD.Comb(2*cnt,cnt-(K+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

結果

テストケース

ソースコード