結果

問題 No.2964 Obstruction Bingo
コンテスト
ユーザー miya145592
提出日時 2024-11-16 17:35:17
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,073 bytes
コンパイル時間 794 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 314,264 KB
最終ジャッジ日時 2024-11-16 17:37:16
合計ジャッジ時間 117,129 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 TLE * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

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:
        if dp[key]==0:
            continue
        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 (pn+1, pm+1) not in ndp:
                ndp[(pn+1, pm+1)] = dp[key] * Q[snc] % MOD
            else:
                ndp[(pn+1, pm+1)] += dp[key] * Q[snc] % MOD
                ndp[(pn+1, pm+1)] %= MOD
            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 (pn+1, pm) not in ndp:
                ndp[(pn+1, pm)] = dp[key] * Q[snc] % MOD
            else:
                ndp[(pn+1, pm)] += dp[key] * Q[snc] % MOD
                ndp[(pn+1, pm)] %= MOD
            if (pn, pm+1) not in ndp:
                ndp[(pn, pm+1)] = dp[key] * Q[smc] % MOD
            else:
                ndp[(pn, pm+1)] += dp[key] * Q[smc] % MOD
                ndp[(pn, pm+1)] %= MOD
            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)
0