結果

問題 No.2964 Obstruction Bingo
コンテスト
ユーザー prin_kemkem
提出日時 2024-11-16 17:25:07
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 2,002 bytes
コンパイル時間 452 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 285,780 KB
最終ジャッジ日時 2024-11-16 17:27:07
合計ジャッジ時間 115,449 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 TLE * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict, deque, Counter
# from functools import cache
# import copy
from itertools import combinations, permutations, product, accumulate, groupby, chain
# from more_itertools import distinct_permutations
from heapq import heapify, heappop, heappush, heappushpop
import math
import bisect
from pprint import pprint
from random import randint, shuffle, randrange
# from sortedcontainers import SortedSet, SortedList, SortedDict
import sys
sys.setrecursionlimit(1000)
input = lambda: sys.stdin.readline().rstrip('\n')
inf = float('inf')
mod1 = 10**9+7
mod2 = 998244353
def ceil_div(x, y): return -(-x//y)

#################################################   

memo = {}
def dp(i, j, k):
    if i >= L and j >= L:
        i -= L
        j -= L
    ijk = i<<20|j<<10|k
    if ijk in memo:
        return memo[ijk]
    if i-j == L:
        return 1, 0
    if j-i == L:
        return 0, 1
    if k == K:
        return 0, 0
    s, t = ord(S[i%L])-ord("a"), ord(T[j%L])-ord("a")
    if s == t:
        rx, ry = 0, 0
        x, y = dp(i, j, k+1)
        x = x*(sa-A[s])%mod2*inv%mod2
        y = y*(sa-A[s])%mod2*inv%mod2
        rx = (rx+x)%mod2; ry = (ry+y)%mod2
        x, y = dp(i+1, j+1, k+1)
        x = x*A[s]%mod2*inv%mod2
        y = y*A[s]%mod2*inv%mod2
        rx = (rx+x)%mod2; ry = (ry+y)%mod2
    else:
        rx, ry = 0, 0
        x, y = dp(i, j, k+1)
        x = x*(sa-A[s]-A[t])%mod2*inv%mod2
        y = y*(sa-A[s]-A[t])%mod2*inv%mod2
        rx = (rx+x)%mod2; ry = (ry+y)%mod2
        x, y = dp(i+1, j, k+1)
        x = x*A[s]%mod2*inv%mod2
        y = y*A[s]%mod2*inv%mod2
        rx = (rx+x)%mod2; ry = (ry+y)%mod2
        x, y = dp(i, j+1, k+1)
        x = x*A[t]%mod2*inv%mod2
        y = y*A[t]%mod2*inv%mod2
        rx = (rx+x)%mod2; ry = (ry+y)%mod2
    memo[ijk] = (rx, ry)
    return rx, ry

L, K = map(int, input().split())
S = input()
T = input()
A = list(map(int, input().split()))
sa = sum(A)
inv = pow(sa, -1, mod2)

x, y = dp(0, 0, 0)
print(x, y)
0