結果
問題 | No.1693 Invasion |
ユーザー |
![]() |
提出日時 | 2021-10-01 21:26:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 158 ms / 2,000 ms |
コード長 | 607 bytes |
コンパイル時間 | 158 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 76,544 KB |
最終ジャッジ日時 | 2024-07-19 10:29:57 |
合計ジャッジ時間 | 3,237 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
mod=998244353 def cmb(n,r): if r<0 or r>n: return 0 return ((g1[n]*g2[r]%mod)*g2[n-r])%mod N=300000 g1=[1]*(N+3) for i in range(2,N+3): g1[i]=g1[i-1]*i%mod g2=[0]*len(g1) g2[-1]=pow(g1[-1],mod-2,mod) for i in range(N+1,-1,-1): g2[i]=g2[i+1]*(i+1)%mod inv=[0]*(N+3) for i in range(1,N+3): inv[i]=g2[i]*g1[i-1]%mod N,M=map(int,input().split()) A=list(map(int,input().split())) DP=[M+1]*(M+1) DP[0]=0 ANS=0 for i in range(M+1): if DP[i]>M: continue ANS=(ANS+cmb(M-DP[i],i-DP[i]))%mod for j in range(N): if i+A[j]>M: continue DP[i+A[j]]=min(DP[i+A[j]],DP[i]+1) print(ANS)