結果
問題 |
No.2111 Sum of Diff
|
ユーザー |
![]() |
提出日時 | 2023-06-08 20:38:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 206 ms / 2,000 ms |
コード長 | 908 bytes |
コンパイル時間 | 384 ms |
コンパイル使用メモリ | 82,488 KB |
実行使用メモリ | 114,372 KB |
最終ジャッジ日時 | 2024-12-31 05:00:10 |
合計ジャッジ時間 | 4,956 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
# a0が使われない回数は2**(N-1)-(N-1)-1 # つまりa0が使われる回数は # 2**N-N-1 - (2**(N-1)-(N-1)-1) # と思ったけど違う問題みたい # 要はある部分列の両端だけが重要 # 左端になる回数は左端からN-1回、N-2回、ーーー、1回、0回 # 右端は左端から0回、1回、ーーー、N-1回 # それで寄与数を求める # いや、間に何個の数字があるかで寄与数が変わってくる # それを考えると左端から2**(N-1)-1, 2**(N-2)-1,,,2**1-1, 2**0-1 N = int(input()) A = list(map(int, input().split())) mod = 998244353 factor = [] for i in range(N): calc = pow(2, i, mod)-1 factor.append(calc) #print(factor) ans = 0 # from left factor_rev = factor[::-1] for i in range(N): ans += A[i]*factor_rev[i] ans %= mod # from right for i in range(N-1, -1, -1): ans -= A[i]*factor[i] ans %= mod print(ans)