fork download
copy 
  1. MOD = 998244353
  2.  
  3. def solve(N, M, S, R, Q, X, Y):
  4.     from collections import Counter, defaultdict
  5.     def modinv(a): return pow(a, MOD - 2, MOD)
  6.     fact = [1] * (N + 1)
  7.     invfact = [1] * (N + 1)
  8.     for i in range(1, N + 1):
  9.         fact[i] = fact[i - 1] * i % MOD
  10.     invfact[N] = modinv(fact[N])
  11.     for i in range(N - 1, -1, -1):
  12.         invfact[i] = invfact[i + 1] * (i + 1) % MOD
  13.  
  14.     def nCr(n, r):
  15.         if n < r or r < 0: return 0
  16.         return fact[n] * invfact[r] % MOD * invfact[n - r] % MOD
  17.  
  18.     chars = set(R)
  19.     prefix = defaultdict(list)
  20.     count = {ch: 0 for ch in chars}
  21.     for i in range(N + 1):
  22.         for ch in chars:
  23.             prefix[ch].append(count[ch])
  24.         if i < N and S[i] in chars:
  25.             count[S[i]] += 1
  26.  
  27.     freqR = Counter(R)
  28.     ans = []
  29.     for i in range(Q):
  30.         l, rpos = X[i] - 1, Y[i]
  31.         total = 1
  32.         for ch in freqR:
  33.             n = prefix[ch][rpos] - prefix[ch][l]
  34.             total = total * nCr(n, freqR[ch]) % MOD
  35.         ans.append(total)
  36.     return ans
  37.  
  38. T = int(input())
  39. for _ in range(T):
  40.     N, M = map(int, input().split())
  41.     S = input().strip()
  42.     R = input().strip()
  43.     Q = int(input())
  44.     X = list(map(int, input().split()))
  45.     Y = list(map(int, input().split()))
  46.     out_ = solve(N, M, S, R, Q, X, Y)
  47.     print(" ".join(map(str, out_)))
  48.  
Success #stdin #stdout 0.11s 14168KB
comments (?)
stdin
copy 
1
8 3
abcdeaab
abc
3
1 2 3
8 4 8
stdout
copy 
6 0 2
https://ideone.com/AS4yZ0
language:
Python 3 (python  3.12)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!