Scribd
Upload
8 views4 pages

Python Solutions for Competitive Programming

The document contains three distinct code snippets that solve different computational problems. The first snippet calculates the number of special subsequences within given constraints, the second finds the maximum remainder from a list of integers based on their parity, and the third computes combinations based on character frequencies in strings. Each snippet includes input handling for multiple test cases.

Uploaded by

Darshan Handi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views4 pages

Python Solutions for Competitive Programming

The document contains three distinct code snippets that solve different computational problems. The first snippet calculates the number of special subsequences within given constraints, the second finds the maximum remainder from a list of integers based on their parity, and the third computes combinations based on character frequencies in strings. Each snippet includes input handling for multiple test cases.

Uploaded by

Darshan Handi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

1:- def solve(N, K, L, R, Sn, Sk):

special = set(Sk)
is_special = [1 if Sn[i] in special else 0 for i in range(N)]
prefix = [0] * (N + 1)
for i in range(1, N + 1):
prefix[i] = prefix[i - 1] + is_special[i - 1]

ft = [0] * (N + 2)

def update(idx, delta):


idx += 1
while idx <= N + 1:
ft[idx] += delta
idx += idx & -idx

def qsum(idx):
idx += 1
res = 0
while idx > 0:
res += ft[idx]
idx -= idx & -idx
return res

update(0, 1)
ans = 0
for b in range(1, N + 1):
cur = prefix[b]
lo = max(0, cur - R)
hi = cur - L
if hi >= lo:
num = qsum(hi) - (qsum(lo - 1) if lo > 0 else 0)
ans += num
update(cur, 1)

return ans

T = int(input())
for _ in range(T):
custom_input1 = list(map(str, input().split()))
N = int(custom_input1[0])
K = int(custom_input1[1])
L = int(custom_input1[2])
R = int(custom_input1[3])
Sn = input()
Sk = input()
out = solve(N, K, L, R, Sn, Sk)
print(out)

—--------------------------------------------------------------------------------------
2:-

import bisect

def find_maximum_remainder(N, A, K):


if K == 1:
return 0
even_mods = []
odd_mods = []
for a in A:
mod = a % K
if mod < 0:
mod += K
if a % 2 == 0:
even_mods.append(mod)
else:
odd_mods.append(mod)
if not even_mods or not odd_mods:
return 0
odd_mods.sort()
max_rem = 0
for x in even_mods:
target = K - x - 1
if target < 0:
continue
idx = bisect.bisect_right(odd_mods, target)
if idx > 0:
y = odd_mods[idx - 1]
max_rem = max(max_rem, x + y)
max_e = max(even_mods)
max_o = max(odd_mods)
if max_e + max_o >= K:
max_rem = max(max_rem, max_e + max_o - K)
return max_rem

—-------------------------------------------------------------------
3rd :- MOD = 998244353
MAXN = 1000005
fact = [1] * MAXN
for i in range(1, MAXN):
fact[i] = fact[i - 1] * i % MOD

def modinv(x):
return pow(x, MOD - 2, MOD)

invfact = [0] * MAXN


invfact[MAXN - 1] = modinv(fact[MAXN - 1])
for i in range(MAXN - 2, -1, -1):
invfact[i] = invfact[i + 1] * (i + 1) % MOD

def binom(n, k):


if k < 0 or k > n:
return 0
return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD

def solve(N, M, S, R, Q, X, Y):


r_freq = [0] * 26
for c in R:
r_freq[ord(c) - ord('a')] += 1

prefix = [[0] * 26 for _ in range(N + 1)]


for i in range(1, N + 1):
c_idx = ord(S[i - 1]) - ord('a')
for j in range(26):
prefix[i][j] = prefix[i - 1][j]
prefix[i][c_idx] += 1

result = []
for q in range(Q):
l, r = X[q], Y[q]
ok = True
ways = 1
for c in range(26):
g = prefix[r][c] - prefix[l - 1][c]
f = r_freq[c]
if g < f:
ok = False
break
ways = ways * binom(g, f) % MOD
if not ok:
ways = 0
[Link](ways)

return result

# Assuming the input reading code is as provided


T = int(input())
for _ in range(T):
line1 = input().split()
N = int(line1[0])
M = int(line1[1])
S = input().strip()
R = input().strip()
Q = int(input())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))
out = solve(N, M, S, R, Q, X, Y)
print(' '.join(map(str, out)))

You might also like