結果
問題 | No.2550 MORE! JUMP! MORE! |
ユーザー |
![]() |
提出日時 | 2023-11-21 17:47:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 141 ms / 2,000 ms |
コード長 | 1,318 bytes |
コンパイル時間 | 207 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 112,888 KB |
最終ジャッジ日時 | 2024-09-26 07:16:03 |
合計ジャッジ時間 | 4,895 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
MOD = 998244353def solve(n, a_list):# k段目にm回目のジャンプで到達する方法 = (k - 1)C(m - 1)# そのあとの方法 = 2 ** (n - k - 1)# k段目が起因の得点の合計 = a_k * sum_{m = 1}^{k} m * (k - 1)C(m - 1)# = a_k * (2 ** (k - 1) + sum_{m = 1}^{k} (m - 1) * (k - 1)C(m - 1))# = a_k * (2 ** (k - 1) + (k - 1) * 2 ** (k - 2))if n == 1:return a_list[0]res = 0pow2_list = [1]for _ in range(n):pow2_list.append((pow2_list[-1] * 2) % MOD)for i in range(1, n + 1):if 2 <= i < n:res += a_list[i - 1] * ((pow2_list[i - 1] + (i - 1) * pow2_list[i - 2]) % MOD) * pow2_list[n - i - 1]elif i == 1:res += a_list[i - 1] * ((pow2_list[i - 1] + (i - 1)) * pow2_list[n - i - 1] % MOD)elif i == n:res += a_list[i - 1] * ((pow2_list[i - 1] + (i - 1) * pow2_list[i - 2]) % MOD)res %= MOD# print(res)return resdef main():n = int(input())a_list = list(map(int, input().split()))res = solve(n, a_list)print(res)def test():assert solve(3, [5, 7, 8]) == 95assert solve(7, [376873723, 252623151, 856139513, 29843394, 373100489, 753241875, 92750716]) == 686211551if __name__ == "__main__":test()main()