結果
問題 |
No.2111 Sum of Diff
|
ユーザー |
![]() |
提出日時 | 2022-11-04 13:50:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 154 ms / 2,000 ms |
コード長 | 1,027 bytes |
コンパイル時間 | 212 ms |
コンパイル使用メモリ | 82,184 KB |
実行使用メモリ | 136,784 KB |
最終ジャッジ日時 | 2024-07-18 13:25:04 |
合計ジャッジ時間 | 3,482 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
N = int(input()) A = list(map(int,input().split())) mod = 998244353 n = len(set(A)) ans = 0 cumJ = 0 base = 1 powmat = [0] * (2 * N) powmat[0] = 1 for i in range(1,2*N): powmat[i] = powmat[i-1] * 2 powmat[i] %=mod for i in range(N): ans -=(cumJ * powmat[N-1-i])%mod * A[i] ans %=mod ''' ans += segJ.sum(0,zipped[i]) * pow(2,N-1-i) * A[i] ans %=mod ''' cumJ += base cumJ %=mod base *=2 base %=mod rev2 = pow(2,mod-2,mod) cumI = [0] * N cumI[0] = 1 for i in range(1,N): cumI[i] = cumI[i-1] * rev2 cumI[i] %=mod def acum(List):#累積和 rev = [0 for _ in range(len(List))] for i in range(len(List)): if i == 0: rev[i] = List[i] else: rev[i] = rev[i-1] + List[i] rev[i] %=mod return rev cumI = acum(cumI) for i in reversed(range(N)): ''' ans -= segI.sum(zipped[i]+1,n) * pow(2,N-1+i) * A[i] ans %=mod ''' ans += ((cumI[N-1]-cumI[i]) * powmat[N-1+i]) % mod * A[i] ans %=mod print(ans)