結果

問題 No.2964 Obstruction Bingo
コンテスト
ユーザー prin_kemkem
提出日時 2024-11-16 17:29:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,092 ms / 2,468 ms
コード長 2,095 bytes
コンパイル時間 529 ms
コンパイル使用メモリ 82,412 KB
実行使用メモリ 280,256 KB
最終ジャッジ日時 2024-11-16 17:31:17
合計ジャッジ時間 54,569 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

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(ijk):
    i, j, k = ijk>>20&0b1111111111, ijk>>10&0b1111111111, ijk&0b1111111111
    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(ijk+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(ijk+0b100000000010000000001)
        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(ijk+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(ijk+0b100000000000000000001)
        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(ijk+0b10000000001)
        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)
print(x, y)
0