fork download
copy 
  1. MOD = 998244353
  2.  
  3. def solve(N, M, S, R, Q, X, Y):
  4.     from collections import Counter
  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.     def nCr(n, r):
  14.         if n < r or r < 0: return 0
  15.         return fact[n] * invfact[r] % MOD * invfact[n - r] % MOD
  16.     chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'
  17.     prefix = {ch: [0] * (N + 1) for ch in chars}
  18.     for i in range(N):
  19.         for ch in prefix:
  20.             prefix[ch][i + 1] = prefix[ch][i] + (1 if S[i] == ch else 0)
  21.     freqR = Counter(R)
  22.     ans = []
  23.     for i in range(Q):
  24.         l, rpos = X[i] - 1, Y[i]
  25.         freqS = {ch: prefix[ch][rpos] - prefix[ch][l] for ch in prefix}
  26.         total = 1
  27.         for ch in freqR:
  28.             total = total * nCr(freqS.get(ch, 0), freqR[ch]) % MOD
  29.         ans.append(total)
  30.     return ans
  31.  
  32. T = int(input())
  33. for _ in range(T):
  34.     N, M = map(int, input().split())
  35.     S = input().strip()
  36.     R = input().strip()
  37.     Q = int(input())
  38.     X = list(map(int, input().split()))
  39.     Y = list(map(int, input().split()))
  40.     out_ = solve(N, M, S, R, Q, X, Y)
  41.     print(" ".join(map(str, out_)))
  42.  
Success #stdin #stdout 0.12s 14124KB
comments (?)
stdin
copy 
1
8 3
abcdeaab
abc
3
1 2 3
8 4 8
stdout
copy 
6 0 2
https://ideone.com/zBpBzP
language:
Python 3 (python  3.12)
created:
3 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!