結果

問題 No.2964 Obstruction Bingo
ユーザー prin_kemkemprin_kemkem
提出日時 2024-11-16 17:19:57
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,002 bytes
コンパイル時間 375 ms
コンパイル使用メモリ 81,836 KB
実行使用メモリ 280,696 KB
最終ジャッジ日時 2024-11-16 17:22:54
合計ジャッジ時間 66,350 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 96 ms
80,376 KB
testcase_01 AC 96 ms
80,384 KB
testcase_02 AC 97 ms
80,388 KB
testcase_03 AC 96 ms
80,500 KB
testcase_04 AC 94 ms
80,340 KB
testcase_05 AC 125 ms
82,060 KB
testcase_06 AC 1,092 ms
250,340 KB
testcase_07 AC 205 ms
94,000 KB
testcase_08 AC 813 ms
206,508 KB
testcase_09 AC 170 ms
89,136 KB
testcase_10 AC 596 ms
160,404 KB
testcase_11 AC 723 ms
192,304 KB
testcase_12 AC 1,747 ms
273,504 KB
testcase_13 AC 317 ms
113,784 KB
testcase_14 AC 276 ms
106,156 KB
testcase_15 AC 141 ms
84,320 KB
testcase_16 AC 513 ms
151,768 KB
testcase_17 AC 398 ms
127,744 KB
testcase_18 AC 377 ms
126,060 KB
testcase_19 AC 667 ms
179,580 KB
testcase_20 AC 847 ms
229,648 KB
testcase_21 AC 1,765 ms
279,556 KB
testcase_22 AC 540 ms
140,948 KB
testcase_23 AC 353 ms
99,172 KB
testcase_24 AC 150 ms
82,024 KB
testcase_25 AC 2,393 ms
280,584 KB
testcase_26 AC 2,374 ms
280,192 KB
testcase_27 AC 2,384 ms
280,608 KB
testcase_28 AC 2,057 ms
278,756 KB
testcase_29 AC 2,450 ms
280,336 KB
testcase_30 AC 2,217 ms
279,288 KB
testcase_31 AC 2,374 ms
280,568 KB
testcase_32 TLE -
testcase_33 AC 2,461 ms
280,496 KB
testcase_34 AC 2,457 ms
280,444 KB
testcase_35 AC 2,090 ms
278,564 KB
testcase_36 AC 2,429 ms
280,268 KB
testcase_37 AC 2,436 ms
280,308 KB
testcase_38 AC 2,414 ms
280,400 KB
testcase_39 AC 2,409 ms
280,340 KB
testcase_40 AC 2,268 ms
279,616 KB
testcase_41 AC 2,152 ms
278,924 KB
testcase_42 TLE -
testcase_43 TLE -
testcase_44 TLE -
testcase_45 AC 330 ms
101,456 KB
testcase_46 AC 99 ms
80,744 KB
testcase_47 AC 95 ms
80,704 KB
testcase_48 AC 322 ms
113,916 KB
testcase_49 AC 287 ms
109,820 KB
testcase_50 AC 706 ms
193,148 KB
testcase_51 AC 2,221 ms
278,900 KB
権限があれば一括ダウンロードができます

ソースコード

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