結果
問題 | No.2626 Similar But Different Name |
ユーザー |
|
提出日時 | 2024-02-11 02:27:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 391 ms / 3,000 ms |
コード長 | 8,151 bytes |
コンパイル時間 | 568 ms |
コンパイル使用メモリ | 82,576 KB |
実行使用メモリ | 124,740 KB |
最終ジャッジ日時 | 2024-09-28 17:25:18 |
合計ジャッジ時間 | 10,327 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
import sys, time, randomfrom collections import deque, Counter, defaultdictinput = lambda: sys.stdin.readline().rstrip()ii = lambda: int(input())mi = lambda: map(int, input().split())li = lambda: list(mi())inf = 2 ** 61 - 1mod = 998244353import string"""Referencehttps://github.com/atcoder/ac-library/blob/master/atcoder/convolution.hpphttps://github.com/atcoder/ac-library/blob/master/atcoder/internal_math.hpphttps://github.com/atcoder/ac-library/blob/master/document_en/convolution.mdhttps://github.com/atcoder/ac-library/blob/master/document_ja/convolution.md"""mod = 998244353def primitive_root(m):if m == 2:return 1if m == 167772161:return 3if m == 469762049:return 3if m == 754974721:return 11if m == 998244353:return 3divs = [0] * 20divs[0] = 2cnt = 1x = (m - 1) // 2while x % 2 == 0:x //= 2i = 3while i * i <= x:if x % i == 0:divs[cnt] = icnt += 1while x % i == 0:x //= ii += 2if x > 1:divs[cnt] = xcnt += 1g = 2while True:ok = Truefor i in range(cnt):if pow(g, (m - 1) // divs[i], m) == 1:ok = Falsebreakif ok:return gg += 1class FFT_INFO:def __init__(self):self.g = primitive_root(mod)self.rank2 = ((mod - 1) & (1 - mod)).bit_length() - 1self.root = [0] * (self.rank2 + 1)self.root[self.rank2] = pow(self.g, (mod - 1) >> self.rank2, mod)self.iroot = [0] * (self.rank2 + 1)self.iroot[self.rank2] = pow(self.root[self.rank2], mod - 2, mod)for i in range(self.rank2 - 1, -1, -1):self.root[i] = self.root[i + 1] * self.root[i + 1] % modself.iroot[i] = self.iroot[i + 1] * self.iroot[i + 1] % modself.rate2 = [0] * max(0, self.rank2 - 1)self.irate2 = [0] * max(0, self.rank2 - 1)prod = 1iprod = 1for i in range(self.rank2 - 1):self.rate2[i] = self.root[i + 2] * prod % modself.irate2[i] = self.iroot[i + 2] * iprod % modprod *= self.iroot[i + 2]prod %= modiprod *= self.root[i + 2]iprod %= modself.rate3 = [0] * max(0, self.rank2 - 2)self.irate3 = [0] * max(0, self.rank2 - 2)prod = 1iprod = 1for i in range(self.rank2 - 2):self.rate3[i] = self.root[i + 3] * prod % modself.irate3[i] = self.iroot[i + 3] * iprod % modprod *= self.iroot[i + 3]prod %= modiprod *= self.root[i + 3]iprod %= modinfo = FFT_INFO()def butterfly(a):n = len(a)h = (n - 1).bit_length()length = 0while length < h:if h - length == 1:p = 1 << (h - length - 1)rot = 1for s in range(1 << length):offset = s << (h - length)for i in range(p):l = a[i + offset]r = a[i + offset + p] * rot % moda[i + offset] = (l + r) % moda[i + offset + p] = (l - r) % modif s + 1 != (1 << length):rot *= info.rate2[(~s & -~s).bit_length() - 1]rot %= modlength += 1else:# 4-basep = 1 << (h - length - 2)rot = 1imag = info.root[2]for s in range(1 << length):rot2 = rot * rot % modrot3 = rot2 * rot % modoffset = s << (h - length)for i in range(p):a0 = a[i + offset]a1 = a[i + offset + p] * rota2 = a[i + offset + 2 * p] * rot2a3 = a[i + offset + 3 * p] * rot3a1na3imag = (a1 - a3) % mod * imaga[i + offset] = (a0 + a2 + a1 + a3) % moda[i + offset + p] = (a0 + a2 - a1 - a3) % moda[i + offset + 2 * p] = (a0 - a2 + a1na3imag) % moda[i + offset + 3 * p] = (a0 - a2 - a1na3imag) % modif s + 1 != (1 << length):rot *= info.rate3[(~s & -~s).bit_length() - 1]rot %= modlength += 2def butterfly_inv(a):n = len(a)h = (n - 1).bit_length()length = h # a[i, i+(n<<length), i+2*(n>>length), ...] is transformedwhile length:if length == 1:p = 1 << (h - length)irot = 1for s in range(1 << (length - 1)):offset = s << (h - length + 1)for i in range(p):l = a[i + offset]r = a[i + offset + p]a[i + offset] = (l + r) % moda[i + offset + p] = (l - r) * irot % modif s + 1 != (1 << (length - 1)):irot *= info.irate2[(~s & -~s).bit_length() - 1]irot %= modlength -= 1else:# 4-basep = 1 << (h - length)irot = 1iimag = info.iroot[2]for s in range(1 << (length - 2)):irot2 = irot * irot % modirot3 = irot2 * irot % modoffset = s << (h - length + 2)for i in range(p):a0 = a[i + offset]a1 = a[i + offset + p]a2 = a[i + offset + 2 * p]a3 = a[i + offset + 3 * p]a2na3iimag = (a2 - a3) * iimag % moda[i + offset] = (a0 + a1 + a2 + a3) % moda[i + offset + p] = (a0 - a1 + a2na3iimag) * irot % moda[i + offset + 2 * p] = (a0 + a1 - a2 - a3) * irot2 % moda[i + offset + 3 * p] = (a0 - a1 - a2na3iimag) * irot3 % modif s + 1 != (1 << (length - 2)):irot *= info.irate3[(~s & -~s).bit_length() - 1]irot %= modlength -= 2def convolution_naive(a, b):n = len(a)m = len(b)ans = [0] * (n + m - 1)if n < m:for j in range(m):for i in range(n):ans[i + j] += a[i] * b[j]ans[i + j] %= modelse:for i in range(n):for j in range(m):ans[i + j] += a[i] * b[j]ans[i + j] %= modreturn ansdef convolution_fft(a, b):a = a.copy()b = b.copy()n = len(a)m = len(b)z = 1 << (n + m - 2).bit_length()a += [0] * (z - n)butterfly(a)b += [0] * (z - m)butterfly(b)for i in range(z):a[i] *= b[i]a[i] %= modbutterfly_inv(a)a = a[:n + m - 1]iz = pow(z, mod - 2, mod)for i in range(n + m - 1):a[i] *= iza[i] %= modreturn adef convolution(a, b):n = len(a)m = len(b)if not n or not m:return []if min(n, m) <= 60:return convolution_naive(a, b)return convolution_fft(a, b)S1 = string.ascii_lowercaseS2 = string.ascii_uppercaseR1 = [0] * 26R2 = [0] * 26for i in range(26):R1[i] = random.randint(1, mod - 1)R2[i] = R1[i] + 1n, m, k = mi()s = input()t = input()a = [0] * nb = [0] * mfor i in range(n):if s[i] in S1:a[i] = R1[S1.index(s[i])]else:a[i] = R2[S2.index(s[i])]for i in range(m):if t[i] in S1:b[i] = R1[S1.index(t[i])]else:b[i] = R2[S2.index(t[i])]C = convolution(a, b[::-1])cnt = 0for i in range(m):cnt += b[i]*b[i]cnt %= modfor i in range(m):cnt += a[i]*a[i]cnt %= modans = 0if 1 <= (cnt - 2 * C[m-1]) % mod <= k:ans += 1for i in range(1, n - m + 1):cnt -= a[i-1] * a[i-1]cnt += a[i+m-1] * a[i+m-1]cnt %= modif 1 <= (cnt - 2 * C[m + i - 1]) % mod <= k:ans += 1print(ans)