結果
問題 | No.2561 みんな大好きmod 998 |
ユーザー | nikoro256 |
提出日時 | 2023-12-08 14:12:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 862 ms / 4,000 ms |
コード長 | 1,121 bytes |
コンパイル時間 | 401 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 78,944 KB |
最終ジャッジ日時 | 2024-09-27 02:49:07 |
合計ジャッジ時間 | 10,224 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 44 |
ソースコード
N,K=map(int,input().split()) A=list(map(int,input().split())) left=A[:N//2] right=A[N//2:] p=998244353 ps=998 exp2=[2**i for i in range(len(A)+1)] def half(lis): lists=[[[] for _ in range(998)] for _ in range(K+1)] for i in range(exp2[len(lis)]): ans_long=0 ans_short=0 count=0 for j in range(len(lis)): if i&1: count+=1 ans_long+=lis[j] ans_long%=p ans_short+=lis[j] ans_short%=ps i>>=1 if K<count: continue lists[count][ans_short].append(ans_long) for i in range(K+1): for j in range(998): lists[i][j].sort() return lists import bisect lefts=half(left) rights=half(right) ans=0 for i in range(K+1): for j in range(998): for t in lefts[i][j]: for k in range(998): lim=(j+k)%ps ans+=bisect.bisect_right(rights[K-i][k],lim-t) ans+=bisect.bisect_right(rights[K-i][k],lim-t+p)-bisect.bisect_left(rights[K-i][k],p-t) ans%=ps print(ans)