結果

問題 No.2791 Beginner Contest
ユーザー るこーそーるこーそー
提出日時 2024-09-24 20:05:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 113 ms / 2,000 ms
コード長 2,423 bytes
コンパイル時間 420 ms
コンパイル使用メモリ 82,436 KB
実行使用メモリ 78,692 KB
最終ジャッジ日時 2024-09-24 20:05:57
合計ジャッジ時間 2,222 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
53,628 KB
testcase_01 AC 39 ms
54,464 KB
testcase_02 AC 79 ms
76,524 KB
testcase_03 AC 37 ms
53,628 KB
testcase_04 AC 37 ms
53,316 KB
testcase_05 AC 38 ms
53,300 KB
testcase_06 AC 95 ms
77,620 KB
testcase_07 AC 70 ms
76,348 KB
testcase_08 AC 72 ms
76,072 KB
testcase_09 AC 107 ms
78,596 KB
testcase_10 AC 108 ms
78,692 KB
testcase_11 AC 47 ms
62,004 KB
testcase_12 AC 113 ms
78,536 KB
testcase_13 AC 47 ms
62,860 KB
testcase_14 AC 43 ms
60,288 KB
testcase_15 AC 46 ms
62,368 KB
testcase_16 AC 38 ms
54,156 KB
testcase_17 AC 37 ms
52,776 KB
testcase_18 AC 47 ms
63,816 KB
testcase_19 AC 48 ms
63,416 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegTree:
    def __init__(self,op,e,v):
        self.n=len(v)
        self.op=op
        self.e=e
        self.size=1<<(self.n-1).bit_length()
        self.node=[self.e]*(2*self.size)
        for i in range(self.n):
            self.node[self.size+i]=v[i]
        for i in range(self.size-1,0,-1):
            self.node[i]=self.op(self.node[i*2],self.node[i*2+1])
    
    def set(self,k,x):
        k+=self.size
        self.node[k]=x
        while k>1:
            k//=2
            self.node[k]=self.op(self.node[2*k],self.node[2*k+1])
    
    def prod_rec(self,a,b,k=1,l=0,r=-1):
        if r<0:r=self.size
        if (r<=a or b<=l):return self.e 
        if (a<=l and r<=b):return self.node[k]
        vl=self.prod_rec(a,b,2*k,l,(l+r)//2)
        vr=self.prod_rec(a,b,2*k+1,(l+r)//2,r)
        return self.op(vl,vr)
    
    def prod(self,l,r):
        l,r=l+self.size,r+self.size
        vl,vr=self.e,self.e
        while l<r:
            if l&1:
                vl=self.op(vl,self.node[l])
                l+=1
            if r&1:
                r-=1
                vr=self.op(vr,self.node[r])
            l>>=1
            r>>=1
        return self.op(vl,vr)
    
    def all_prod(self):
        return self.node[1]
    
    def get(self,k):
        return self.node[self.size+k]
    
    def max_right(self,l,f):
      if l==self.n:return self.n
      l+=self.size
      sm=self.e
      while True:
        while l&0:l>>=1
        if not f(self.op(sm,self.node[l])):
          while l<self.size:
            l<<=1
            if f(self.op(sm,self.node[l])):
              sm=self.op(sm,self.node[l])
              l+=1
          return l-self.size
        sm=self.op(sm,self.node[l])
        l+=1
        if l&-l==l:break
      return self.n
    
    def min_left(self,r,f):
      if r==0:return 0
      r+=self.size
      sm=self.e
      while True:
        r-=1
        while r>1 and r&1:r>>=1
        if not f(self.op(self.node[r],sm)):
          while r<self.size:
            r=2*r+1
            if f(self.op(self.node[r].sm)):
              sm=self.op(self.node[r],sm)
              r-=1
          return r+1-self.size
        sm=self.op(self.node[r],sm)
        if r&-r==r:break
      return 0
  
def op(x,y):return (x+y)%MOD
e=0

MOD=998244353

n,k=map(int,input().split())

dp=SegTree(op,e,[0]*(n+1))
dp.set(0,1)
for i in range(k,n+1):
    dp.set(i,dp.prod(0,i-k+1))
    
print(dp.all_prod()%MOD)
0