結果
問題 | No.2964 Obstruction Bingo |
ユーザー | prin_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 |
ソースコード
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)