結果
問題 | No.1239 Multiplication -2 |
ユーザー |
|
提出日時 | 2020-09-25 23:00:44 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,298 ms / 2,000 ms |
コード長 | 712 bytes |
コンパイル時間 | 403 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 21,612 KB |
最終ジャッジ日時 | 2024-06-28 07:14:38 |
合計ジャッジ時間 | 17,685 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
N = int(input()) As = list(map(int, input().split())) MOD = 998244353 half = pow(2, MOD - 2, MOD) alphas = [0] * 5 dp = [0] * (N + 1) dpsum = 0 prod = 1 for i, A in enumerate(As): prod *= A if not (-2 <= prod <= 2): prod = 0 if prod == -2: dp[i + 1] += pow(2, MOD - 2 - i, MOD) alphas[1] += 1 new_alphas = [0] * 5 for j in range(-2, 3): index = j * A if not (-2 <= index <= 2): index = 0 new_alphas[index] += alphas[j] * half new_alphas[index] %= MOD alphas = new_alphas dp[i + 1] += (dpsum + alphas[-2]) % MOD dp[i + 1] %= MOD dpsum += dp[i + 1] dpsum = dpsum * half % MOD # print(dp) print(dp[-1])