結果
問題 | No.2964 Obstruction Bingo |
ユーザー |
|
提出日時 | 2024-11-16 17:45:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,387 ms / 2,468 ms |
コード長 | 2,703 bytes |
コンパイル時間 | 338 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 131,692 KB |
最終ジャッジ日時 | 2024-11-16 17:46:46 |
合計ジャッジ時間 | 64,713 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
import sys input = sys.stdin.readline MOD = 998244353 L, K = map(int, input().split()) S = input().strip() T = input().strip() A = list(map(int, input().split())) C = sum(A) base = pow(C, MOD-2, MOD) Q = [] for a in A: Q.append(a*base%MOD) #print(Q) dp = dict() dp[(0, 0)] = 1 X = 0 Y = 0 for i in range(K): ndp = dict() for key in dp: pn, pm = key if pn-pm==L: X += dp[key] X %= MOD continue if pm-pn==L: Y += dp[key] Y %= MOD continue sn = S[pn%L] sm = T[pm%L] if sn==sm: snc = ord(sn)-ord('a') if Q[snc]>0: npn = pn+1 npm = pm+1 if npn>=L and npm>=L: npn-=L npm-=L if (npn, npm) not in ndp: ndp[(npn, npm)] = dp[key] * Q[snc] % MOD else: ndp[(npn, npm)] += dp[key] * Q[snc] % MOD ndp[(npn, npm)] %= MOD if (1-Q[snc])%MOD>0: if (pn, pm) not in ndp: ndp[(pn, pm)] = dp[key] * (1-Q[snc]) % MOD else: ndp[(pn, pm)] += dp[key] * (1-Q[snc]) % MOD ndp[(pn, pm)] %= MOD else: snc = ord(sn)-ord('a') smc = ord(sm)-ord('a') if Q[snc]>0: npn = pn+1 npm = pm if npn>=L and npm>=L: npn-=L npm-=L if (npn, npm) not in ndp: ndp[(npn, npm)] = dp[key] * Q[snc] % MOD else: ndp[(npn, npm)] += dp[key] * Q[snc] % MOD ndp[(npn, npm)] %= MOD if Q[smc]>0: npn = pn npm = pm+1 if npn>=L and npm>=L: npn-=L npm-=L if (npn, npm) not in ndp: ndp[(npn, npm)] = dp[key] * Q[smc] % MOD else: ndp[(npn, npm)] += dp[key] * Q[smc] % MOD ndp[(npn, npm)] %= MOD if (1-Q[snc]-Q[smc])%MOD>0: if (pn, pm) not in ndp: ndp[(pn, pm)] = dp[key] * (1-Q[snc]-Q[smc]) % MOD else: ndp[(pn, pm)] += dp[key] * (1-Q[snc]-Q[smc]) % MOD ndp[(pn, pm)] %= MOD dp = ndp #print(dp) #print(X, Y) for key in dp: pn, pm = key if pn-pm==L: X += dp[key] X %= MOD continue if pm-pn==L: Y += dp[key] Y %= MOD continue print(X, Y)