fork download
copy 
  1. MOD = 998244353
  2.  
  3. def solve(N, M, S, R, Q, X, Y):
  4.     from collections import Counter
  5.     prefix = {ch: [0] * (N + 1) for ch in set(S + R)}
  6.     for i in range(N):
  7.         for ch in prefix:
  8.             prefix[ch][i + 1] = prefix[ch][i] + (1 if S[i] == ch else 0)
  9.     freqR = Counter(R)
  10.     ans = []
  11.     for i in range(Q):
  12.         l, r = X[i] - 1, Y[i]
  13.         freqS = {ch: prefix[ch][r] - prefix[ch][l] for ch in prefix}
  14.         ways = 1
  15.         for ch in freqR:
  16.             if freqS[ch] < freqR[ch]:
  17.                 ways = 0
  18.                 break
  19.         if ways != 0:
  20.             total = 1
  21.             for ch in freqR:
  22.                 n = freqS[ch]
  23.                 r = freqR[ch]
  24.                 val = 1
  25.                 for j in range(r):
  26.                     val = val * (n - j) % MOD
  27.                 total = (total * val) % MOD
  28.             ways = total
  29.         ans.append(ways % MOD)
  30.     print(" ".join(map(str, ans)))
  31.  
  32. if __name__ == "__main__":
  33.     T = int(input())
  34.     for _ in range(T):
  35.         N, M = map(int, input().split())
  36.         S = input().strip()
  37.         R = input().strip()
  38.         Q = int(input())
  39.         X = list(map(int, input().split()))
  40.         Y = list(map(int, input().split()))
  41.         solve(N, M, S, R, Q, X, Y)
  42.  
Success #stdin #stdout 0.11s 14108KB
comments (?)
stdin
copy 
1
8 3
abcdeaab
abc
3
1 2 3
8 4 8
stdout
copy 
6 0 2
https://ideone.com/OlnTG2
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!