結果

問題 No.1696 Nonnil
ユーザー sasa8uyauya
提出日時 2025-03-08 05:20:18
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 973 bytes
コンパイル時間 472 ms
コンパイル使用メモリ 82,220 KB
実行使用メモリ 78,384 KB
最終ジャッジ日時 2025-03-08 05:20:31
合計ジャッジ時間 12,722 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10 TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
p+=[(-1,-1)]
M=998244353
q=[[[0]*(k+1),[0]*(k+1)] for i in range(m+1)]
q[-1][0][0]=1
for h in range(m):
  l,r=p[h]
  for i in range(-1,h):
    ll,rr=p[i]
    for j in range(k+1):
      if rr<l:
        if j+(r-l+1)<=k:
          q[h][0][j+(r-l+1)]+=q[i][1][j]
          q[h][0][j+(r-l+1)]%=M
          q[h][1][j+(r-l+1)]+=q[i][0][j]
          q[h][1][j+(r-l+1)]%=M
      else:
        if j+(r-rr)<=k:
          q[h][0][j+(r-rr)]+=q[i][1][j]
          q[h][0][j+(r-rr)]%=M
          q[h][1][j+(r-rr)]+=q[i][0][j]
          q[h][1][j+(r-rr)]%=M
a=pow(k,n,M)
for i in range(m):
  for j in range(k+1):
    a-=pow(k-j,n,M)*q[i][1][j]
    a+=pow(k-j,n,M)*q[i][0][j]
    a%=M
print(a)
0