LR-remainders (Codeforces 1932C)
Tags: Math, two pointers

You are given an array $$$a$$$ of length $$$n$$$, a positive integer $$$m$$$, and a string of commands of length $$$n$$$. Each command is either the character 'L' or the character 'R'.Process all $$$n$$$ commands in the order they are written in the string $$$s$$$. Processing a command is done as follows:  First, output the remainder of the product of all elements of the array $$$a$$$ when divided by $$$m$$$.  Then, if the command is 'L', remove the leftmost element from the array $$$a$$$, if the command is 'R', remove the rightmost element from the array $$$a$$$. Note that after each move, the length of the array $$$a$$$ decreases by $$$1$$$, and after processing all commands, it will be empty.Write a program that will process all commands in the order they are written in the string $$$s$$$ (from left to right).

Input: The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the input. Then descriptions of $$$t$$$ test cases follow.Each test case of the input is given by three lines.The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2\cdot10^5, 1 \le m \le 10^4$$$) — the initial length of the array $$$a$$$ and the value to take the remainder by.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^4$$$) — the elements of the array $$$a$$$.The third line contains a string $$$s$$$ consisting of $$$n$$$ characters 'L' and 'R'.It is guaranteed that the sum of the values of $$$n$$$ for all test cases in a test does not exceed $$$2\cdot10^5$$$.

Output: For each test case, output $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$, where $$$b_i$$$ is the remainder when dividing the product of all elements of the current state of the array $$$a$$$ by $$$m$$$ at the beginning of the execution of the $$$i$$$-th command.

Note: In the first test case of the example: $$$3 \cdot 1 \cdot 4 \cdot 2 \bmod 6 = 24 \bmod 6 = 0$$$; $$$s_1 = \text{L}$$$, so we remove the first element and get the array $$$[1, 4, 2]$$$; $$$1 \cdot 4 \cdot 2 \bmod 6 = 8 \bmod 6 = 2$$$; $$$s_2 = \text{R}$$$, so we remove the last element and get the array $$$[1, 4]$$$; $$$1 \cdot 4 \bmod 6 = 4 \bmod 6 = 4$$$; $$$s_3 = \text{R}$$$, so we remove the last element and get the array $$$[1]$$$; $$$1 \bmod 6 = 1$$$; $$$s_4 = \text{L}$$$, so we remove the first element and get an empty array.

Sample Inputs:
4
4 6
3 1 4 2
LRRL
5 1
1 1 1 1 1
LLLLL
6 8
1 2 3 4 5 6
RLLLRR
1 10000
10000
R

Sample Outputs:
0 2 4 1 
0 0 0 0 0 
0 0 0 4 4 4 
0

Solution (Python):
from collections import *
from math import *
from heapq import *
import sys
from os import path

def input():
    return sys.stdin.readline().strip()

def input_int():
    return int(input())

def input_list(delimiter=' '):
    return list(map(int, input().split(delimiter)))

def input_string():
    return input()

def solve():
    (n, m) = input_list()
    A = input_list()
    s = input_string()
    ans = []
    (i, j) = (0, n - 1)
    for c in s:
        if c == 'L':
            ans.append(A[i])
            i += 1
        else:
            ans.append(A[j])
            j -= 1
    p = 1
    for i in range(n - 1, -1, -1):
        ans[i] = ans[i] * p % m
        p = ans[i]
    return ' '.join(map(str, ans))

def main():
    testcases = input_int()
    for _ in range(testcases):
        print(solve())
if __name__ == '__main__':
    if path.exists('input.txt'):
        sys.stdin = open('input.txt', 'r')
        sys.stdout = open('output.txt', 'w')
    main()

Solution (Python):
def solution(arr, n, m, s):
    b = [0] * n
    mod_arr = [0] * n
    for i in range(n):
        mod_arr[i] = arr[i] % m
    remaining_index = s[:-1].count('L')
    last_num = arr[remaining_index]
    prod = last_num % m
    b[-1] = prod
    curr_index_l = remaining_index
    curr_index_r = remaining_index
    for i in range(n - 2, -1, -1):
        command = s[i]
        if command == 'L':
            curr_index_l -= 1
            prod *= mod_arr[curr_index_l]
        elif command == 'R':
            curr_index_r += 1
            prod *= mod_arr[curr_index_r]
        prod = prod % m
        b[i] = prod
    print(' '.join(map(str, b)))
t = int(input())
for _ in range(t):
    (n, m) = map(int, input().split())
    a = list(map(int, input().split()))
    s = input()
    solution(a, n, m, s)

Solution (Python):
from sys import stdin, stdout

def main():
    input = stdin.readline
    print = stdout.write
    t = int(input().strip())
    res = []
    for _ in range(t):
        (n, m) = map(int, input().strip().split())
        nums = list(map(int, input().strip().split()))
        command = input().strip()
        left = 0
        right = n - 1
        tmp = []
        nums_order = []
        for i in range(n):
            if command[i] == 'L':
                nums_order.append(nums[left])
                left += 1
            else:
                nums_order.append(nums[right])
                right -= 1
        product = 1
        for _ in range(n):
            product = product * nums_order.pop() % m
            tmp.append(product)
        print(' '.join(map(str, reversed(tmp))) + '\n')
main()