結果
問題 | No.2964 Obstruction Bingo |
ユーザー |
|
提出日時 | 2024-11-16 17:46:32 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,892 bytes |
コンパイル時間 | 400 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 77,440 KB |
最終ジャッジ日時 | 2024-11-16 17:46:44 |
合計ジャッジ時間 | 9,727 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 WA * 44 |
ソースコード
from collections import deque, defaultdict as ddfrom copy import deepcopyfrom heapq import heappop, heappush, heappushpop, heapifyINF = 1 << 60MOD = 998244353def fast_mod_pow(x, p, m):res = 1t = xz = pwhile z > 0:if z % 2 == 1:res = (res * t) % mt = (t * t) % mz //= 2return resdef extended_gcd(a, b):if b == 0:return a, 1, 0else:g, x, y = extended_gcd(b, a % b)return g, y, x - (a // b) * ydef mod_inverse(a, m):_, x, _ = extended_gcd(a, m)return (x % m + m) % mdef main():l, k = map(int, input().split())s = list(input())t = list(input())a = list(map(int, input().split()))ac = sum(a)div = mod_inverse(ac, MOD)for i in range(26):a[i] = (a[i]*div)%MODz = ord("a")for i in range(l):s[i] = ord(s[i])-zt[i] = ord(t[i])-zdp = [[0 for _ in range(2*l+1)]for _ in range(l)]dp[0][l] = 1for _ in range(k):ndp = [[0 for _ in range(2 * l + 1)] for _ in range(l)]for i in range(l):ndp[i][0] = dp[i][0]ndp[i][-1] = dp[i][-1]for j in range(1, 2*l):idx1, idx2 = s[i], t[(i+j-l)%l]if idx1==idx2:ndp[i][j] = (ndp[i][j]+dp[i][j]*(MOD+1-a[idx1]))%MODndp[(i+1)%l][j] = (ndp[(i+1)%l][j]+dp[i][j]*a[idx1])%MODelse:ndp[i][j] = (ndp[i][j]+dp[i][j]*(2*MOD+1-a[idx1]-a[idx2])%MOD)%MODndp[(i+1)%l][j+1] = (ndp[(i+1)%l][j+1]+dp[i][j]*a[idx1])%MODndp[i][j-1] = (ndp[i][j-1]+dp[i][j]*a[idx2])%MODdp = ndpans1, ans2 = 0, 0for i in range(l):ans1 = (ans1+dp[i][2*l])%MODans2 = (ans2+dp[i][0])%MODprint(ans1, ans2)if __name__ == "__main__":main()