結果

問題 No.2964 Obstruction Bingo
ユーザー prin_kemkemprin_kemkem
提出日時 2024-11-16 17:18:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,006 bytes
コンパイル時間 370 ms
コンパイル使用メモリ 81,904 KB
実行使用メモリ 198,004 KB
最終ジャッジ日時 2024-11-16 17:18:31
合計ジャッジ時間 14,529 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 88 ms
80,256 KB
testcase_01 AC 89 ms
80,148 KB
testcase_02 AC 93 ms
80,000 KB
testcase_03 AC 93 ms
80,112 KB
testcase_04 AC 92 ms
80,256 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 190 ms
93,876 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 AC 565 ms
192,072 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 428 ms
151,452 KB
testcase_17 AC 358 ms
127,508 KB
testcase_18 WA -
testcase_19 AC 522 ms
179,436 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 483 ms
140,920 KB
testcase_23 AC 348 ms
98,912 KB
testcase_24 AC 143 ms
81,792 KB
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 AC 92 ms
80,488 KB
testcase_48 AC 138 ms
84,920 KB
testcase_49 WA -
testcase_50 WA -
testcase_51 WA -
権限があれば一括ダウンロードができます

ソースコード

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(2000000)
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<<16|j<<8|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