#929484 (PyPy3) No.1388 Less than K

提出ソース

結果

問題	No.1388 Less than K
ユーザー	vwxyz
提出日時	2023-11-19 01:40:46
言語	PyPy3 (7.3.15)
結果	TLE
実行時間	-
コード長	4,378 bytes
コンパイル時間	583 ms
コンパイル使用メモリ	82,432 KB
実行使用メモリ	128,812 KB
最終ジャッジ日時	2024-09-26 06:02:01
合計ジャッジ時間	24,725 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	153 ms 96,424 KB
testcase_01	AC	154 ms 89,272 KB
testcase_02	AC	157 ms 89,492 KB
testcase_03	AC	157 ms 89,300 KB
testcase_04	AC	169 ms 89,824 KB
testcase_05	AC	193 ms 90,468 KB
testcase_06	AC	185 ms 90,300 KB
testcase_07	AC	157 ms 89,568 KB
testcase_08	AC	216 ms 91,668 KB
testcase_09	AC	179 ms 90,424 KB
testcase_10	AC	175 ms 90,148 KB
testcase_11	AC	175 ms 90,216 KB
testcase_12	AC	209 ms 91,976 KB
testcase_13	AC	231 ms 93,188 KB
testcase_14	AC	264 ms 94,220 KB
testcase_15	AC	421 ms 97,540 KB
testcase_16	AC	519 ms 100,856 KB
testcase_17	AC	721 ms 103,820 KB
testcase_18	AC	1,094 ms 111,500 KB
testcase_19	AC	1,509 ms 117,536 KB
testcase_20	AC	1,591 ms 117,816 KB
testcase_21	AC	258 ms 117,460 KB
testcase_22	AC	208 ms 112,164 KB
testcase_23	AC	207 ms 99,404 KB
testcase_24	AC	231 ms 104,952 KB
testcase_25	AC	242 ms 107,576 KB
testcase_26	AC	231 ms 109,584 KB
testcase_27	AC	204 ms 103,752 KB
testcase_28	AC	200 ms 104,732 KB
testcase_29	AC	190 ms 104,752 KB
testcase_30	AC	168 ms 90,248 KB
testcase_31	AC	176 ms 93,288 KB
testcase_32	AC	157 ms 89,664 KB
testcase_33	AC	211 ms 115,036 KB
testcase_34	AC	209 ms 114,528 KB
testcase_35	AC	205 ms 111,872 KB
testcase_36	AC	236 ms 114,628 KB
testcase_37	AC	216 ms 118,220 KB
testcase_38	AC	299 ms 118,044 KB
testcase_39	AC	246 ms 114,528 KB
testcase_40	AC	269 ms 111,932 KB
testcase_41	AC	403 ms 128,632 KB
testcase_42	AC	242 ms 118,064 KB
testcase_43	AC	2,649 ms 128,812 KB
testcase_44	AC	2,367 ms 128,296 KB
testcase_45	TLE	-
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<=300:
    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):
            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

結果

テストケース

ソースコード