結果

問題 No.1696 Nonnil
コンテスト
ユーザー sasa8uyauya
提出日時 2025-03-08 06:34:17
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,182 bytes
コンパイル時間 429 ms
コンパイル使用メモリ 82,376 KB
実行使用メモリ 266,564 KB
最終ジャッジ日時 2025-03-08 06:35:24
合計ジャッジ時間 12,959 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 29 TLE * 4 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class FenwickTree:
  def __init__(self,n):
    self._n=n
    self.data=[0]*n
  
  def add(self,p,x):
    p+=1
    while p<=self._n:
      self.data[p-1]+=x
      p+=p&(-p)
  
  def sum(self,l,r):
    return self._sum(r)-self._sum(l)
  
  def _sum(self,r):
    s=0
    while r>0:
      s+=self.data[r-1]
      r-=r&(-r)
    return s


n,k=map(int,input().split())
m=int(input())
X=k
p=[X]*k
for _ in range(m):
  l,r=map(int,input().split())
  l-=1
  r-=1
  p[l]=min(p[l],r)
for i in range(k):
  for j in range(i+1,k):
    if i!=j and p[i]<X and p[j]<X and p[i]>=p[j]:
      p[i]=X
p=[(i,p[i]) for i in range(k) if p[i]<X]
m=len(p)
M=998244353
q=[[FenwickTree(k) for j in range(2)] for i in range(k+1)]
for i in range(m):
  l,r=p[i]
  q[r-l+1][1].add(r,1)
  for j in range(k+1):
    if j+(r-l+1)<=k:
      q[j+(r-l+1)][0].add(r,q[j][1].sum(0,l))
      q[j+(r-l+1)][1].add(r,q[j][0].sum(0,l))
  for j in range(k+1):
    for rr in range(l,r):
      if j+(r-rr)<=k:
        q[j+(r-rr)][0].add(r,q[j][1].sum(rr,rr+1))
        q[j+(r-rr)][1].add(r,q[j][0].sum(rr,rr+1))
a=pow(k,n,M)
for i in range(k+1):
  a-=pow(k-i,n,M)*q[i][1].sum(0,k)
  a+=pow(k-i,n,M)*q[i][0].sum(0,k)
  a%=M
print(a)
0