結果

問題 No.2964 Obstruction Bingo
ユーザー prin_kemkemprin_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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 85 ms
80,196 KB
testcase_01 AC 85 ms
80,236 KB
testcase_02 AC 117 ms
80,384 KB
testcase_03 AC 82 ms
80,076 KB
testcase_04 AC 83 ms
80,192 KB
testcase_05 AC 109 ms
82,176 KB
testcase_06 AC 898 ms
250,120 KB
testcase_07 AC 177 ms
93,360 KB
testcase_08 AC 637 ms
204,640 KB
testcase_09 AC 155 ms
88,828 KB
testcase_10 AC 442 ms
159,832 KB
testcase_11 AC 568 ms
191,928 KB
testcase_12 AC 1,380 ms
273,404 KB
testcase_13 AC 261 ms
113,908 KB
testcase_14 AC 228 ms
105,968 KB
testcase_15 AC 122 ms
84,260 KB
testcase_16 AC 436 ms
149,828 KB
testcase_17 AC 318 ms
128,020 KB
testcase_18 AC 303 ms
126,672 KB
testcase_19 AC 534 ms
179,416 KB
testcase_20 AC 700 ms
229,520 KB
testcase_21 AC 1,403 ms
279,340 KB
testcase_22 AC 416 ms
142,276 KB
testcase_23 AC 221 ms
97,916 KB
testcase_24 AC 125 ms
81,768 KB
testcase_25 AC 1,921 ms
279,868 KB
testcase_26 AC 2,016 ms
279,884 KB
testcase_27 AC 1,946 ms
279,656 KB
testcase_28 AC 1,836 ms
278,676 KB
testcase_29 AC 2,008 ms
279,924 KB
testcase_30 AC 1,868 ms
278,960 KB
testcase_31 AC 2,014 ms
279,404 KB
testcase_32 AC 2,092 ms
280,188 KB
testcase_33 AC 2,045 ms
279,964 KB
testcase_34 AC 2,008 ms
280,256 KB
testcase_35 AC 1,832 ms
278,800 KB
testcase_36 AC 2,034 ms
280,116 KB
testcase_37 AC 1,987 ms
280,040 KB
testcase_38 AC 2,001 ms
280,124 KB
testcase_39 AC 1,998 ms
279,620 KB
testcase_40 AC 1,857 ms
279,376 KB
testcase_41 AC 1,852 ms
278,848 KB
testcase_42 AC 2,009 ms
279,704 KB
testcase_43 AC 1,994 ms
279,880 KB
testcase_44 AC 2,017 ms
279,968 KB
testcase_45 AC 205 ms
97,164 KB
testcase_46 AC 89 ms
80,384 KB
testcase_47 AC 85 ms
80,384 KB
testcase_48 AC 291 ms
113,936 KB
testcase_49 AC 229 ms
109,600 KB
testcase_50 AC 569 ms
191,532 KB
testcase_51 AC 1,828 ms
278,616 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(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