結果
問題 | No.2062 Sum of Subset mod 999630629 |
ユーザー |
![]() |
提出日時 | 2022-08-26 10:04:38 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,684 ms / 5,000 ms |
コード長 | 587 bytes |
コンパイル時間 | 206 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 281,204 KB |
最終ジャッジ日時 | 2024-10-14 01:02:33 |
合計ジャッジ時間 | 13,473 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
n=int(input()) a=list(map(int,input().split())) a.sort(reverse=True) mod=998244353 ans=pow(2,n-1,mod)*sum(a)%mod p=999630629 k=sum(a)-p if k>=0: dp=[0]*(k+1) dp[0]=1 newdp=[0]*(k+1) ch=set() ch.add(0) for x in a: newch=set() for s in ch: newdp[s]+=dp[s] newdp[s]%=mod newch.add(s) if s+x<=k: newdp[s+x]+=dp[s] newdp[s+x]%=mod newch.add(s+x) for s in ch:dp[s]=0 dp,newdp=newdp,dp ch=newch ans-=p*sum(dp) print(ans%mod)