結果

問題 No.2964 Obstruction Bingo
ユーザー miya145592miya145592
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
57,728 KB
testcase_01 AC 38 ms
244,440 KB
testcase_02 AC 40 ms
58,496 KB
testcase_03 AC 40 ms
247,280 KB
testcase_04 AC 40 ms
57,472 KB
testcase_05 AC 400 ms
272,836 KB
testcase_06 TLE -
testcase_07 AC 496 ms
281,804 KB
testcase_08 TLE -
testcase_09 AC 930 ms
250,440 KB
testcase_10 TLE -
testcase_11 AC 1,201 ms
310,780 KB
testcase_12 TLE -
testcase_13 AC 1,631 ms
314,264 KB
testcase_14 AC 1,907 ms
122,196 KB
testcase_15 AC 405 ms
281,088 KB
testcase_16 AC 1,180 ms
107,604 KB
testcase_17 AC 822 ms
294,596 KB
testcase_18 AC 1,426 ms
111,836 KB
testcase_19 AC 1,162 ms
306,096 KB
testcase_20 TLE -
testcase_21 TLE -
testcase_22 AC 681 ms
95,448 KB
testcase_23 AC 304 ms
280,584 KB
testcase_24 AC 139 ms
82,448 KB
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
testcase_30 TLE -
testcase_31 TLE -
testcase_32 TLE -
testcase_33 TLE -
testcase_34 TLE -
testcase_35 TLE -
testcase_36 TLE -
testcase_37 TLE -
testcase_38 TLE -
testcase_39 TLE -
testcase_40 TLE -
testcase_41 TLE -
testcase_42 TLE -
testcase_43 TLE -
testcase_44 TLE -
testcase_45 AC 1,969 ms
124,244 KB
testcase_46 AC 45 ms
244,084 KB
testcase_47 AC 135 ms
83,400 KB
testcase_48 AC 45 ms
59,136 KB
testcase_49 AC 2,300 ms
137,092 KB
testcase_50 TLE -
testcase_51 TLE -
権限があれば一括ダウンロードができます

ソースコード

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