結果
問題 | No.1239 Multiplication -2 |
ユーザー |
![]() |
提出日時 | 2020-09-25 22:29:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 307 ms / 2,000 ms |
コード長 | 744 bytes |
コンパイル時間 | 192 ms |
コンパイル使用メモリ | 82,816 KB |
実行使用メモリ | 104,832 KB |
最終ジャッジ日時 | 2024-06-28 06:56:36 |
合計ジャッジ時間 | 6,937 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
MOD = 998244353 n = int(input()) a = list(map(int, input().split())) dp = [[1, 0], [0, 0]] # [abs is 2][sig is neg] ans = 0 for z, x in enumerate(a): ndp = [[0, 0], [0, 0]] if x == 2: ndp[1][0] = dp[0][0] ndp[1][1] = dp[0][1] elif x == -2: ndp[1][0] = dp[0][1] ndp[1][1] = dp[0][0] elif x == 1: for i in range(2): for j in range(2): ndp[i][j] = dp[i][j] elif x == -1: for i in range(2): for j in range(2): ndp[i][j] = dp[i][1-j] ans = (ans + ndp[1][1] * pow(2, max(0, n - 2 - z), MOD)) % MOD ndp[0][0] += pow(2, z, MOD) ndp[0][0] %= MOD dp = ndp q = pow(2, n-1, MOD) print(ans * pow(q, MOD-2, MOD) % MOD)