結果
問題 | No.1239 Multiplication -2 |
ユーザー |
![]() |
提出日時 | 2020-09-25 22:36:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 370 ms / 2,000 ms |
コード長 | 1,660 bytes |
コンパイル時間 | 165 ms |
コンパイル使用メモリ | 81,664 KB |
実行使用メモリ | 103,552 KB |
最終ジャッジ日時 | 2024-06-28 07:01:38 |
合計ジャッジ時間 | 7,249 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
""" -2になる各区間に関して いくつ出現するかを求めればいい? 各2 or -2から左右を見ていく 0か|2|にぶつかったら終わり 各場所最大2回しか見ないのでおk 全ての区間の個数も数え上げる 左端がいくつあるか答えればいい ある場所を左端にするとき、残りの切り方を数えればいいのでおわり A,B個左右に残ってる場合の通り数は 2^(A-1) * 2^(B-1) """ from sys import stdin import sys def inverse(a,mod): #aのmodを法にした逆元を返す return pow(a,mod-2,mod) def ppow(x,y,mod): if y >= 0: return pow(x,y,mod) else: return 1 N = int(stdin.readline()) a = list(map(int,stdin.readline().split())) if N == 1: if a[0] == -2: print (1) else: print (0) sys.exit() mod = 998244353 ALL = ( pow(2,N-1,mod) + (N-1) * pow(2,N-2,mod) ) % mod half = inverse(2,mod) ans = 0 for i in range(N): if abs(a[i]) != 2: continue dic = {} dic[2] = 0 dic[-2] = 0 dic[a[i]] = ppow(2,N-1-i-1,mod) now = a[i] for j in range(i+1,N): if abs(a[j]) != 1: break now *= a[j] dic[now] += ppow(2,N-j-1-1,mod) ans += dic[-2] * ppow(2,i-1,mod) now = 1 for j in range(i-1,-1,-1): if abs(a[j]) != 1: break now *= a[j] if now == 1: ans += dic[-2] * ppow(2,j-1,mod) else: ans += dic[2] * ppow(2,j-1,mod) ans %= mod #print (ans,dic) #print (ans , ALL , file=sys.stderr) print (ans * inverse(pow(2,N-1,mod),mod) % mod)