結果

問題 No.2964 Obstruction Bingo
ユーザー miya145592
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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:
        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)
0