LR-remainders

题面翻译

题目描述

给定一个长度为 $n$ 的数组 $a$，一个正整数 $m$，以及一个长度为 $n$ 的命令字符串。每个命令要么是字符 L，要么是字符 R。

按照字符串 $s$ 中写入的顺序处理所有 $n$ 个命令。处理命令的步骤如下：

首先，输出数组 $a$ 中所有元素的乘积除以 $m$ 的余数。
然后，如果命令是 L，则从数组 $a$ 中移除最左边的元素；如果命令是 R，则从数组 $a$ 中移除最右边的元素。
请注意，每次移动后，数组 $a$ 的长度减少 $1$，并且在处理所有命令后，数组将为空。

编写一个程序，按照字符串 $s$ 中写入的顺序从左到右处理所有命令。

输入格式

第一行包含一个整数 $t$（$1\le t\le10^4$），表示输入中的测试数据数量。然后是 $t$ 个测试数据的描述。

输入的每个测试数据分 $3$ 出。

第一行包含两个整数 $n$ 和 $m$（$1\le n\le2\cdot10^5,1\le m\le10^4$）——数组 $a$ 的初始长度和取余数的值。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le10^4$），数组 $a$ 的元素。

第三行包含一个由 $ n $ 个字符 L 和 R 组成的字符串 $s$。

保证一个测试用例中所有 $n$ 值的总和不超过 $2\cdot10^5$。

输出格式

对于每个测试用例，输出 $n$ 个整数 $b_1,b_2,\dots,b_n$，其中 $b_i$ 是在执行第 $i$ 个命令时，当前数组 $a$ 的所有元素的乘积除以 $m$ 的余数。

样例解释

在示例的第一个测试用例中：

• $ 3 \cdot 1 \cdot 4 \cdot 2 \bmod 6 = 24 \bmod 6 = 0 $；
• $ s_1 = \text{L} $，因此我们移除第一个元素，得到数组 $ [1, 4, 2] $；
• $ 1 \cdot 4 \cdot 2 \bmod 6 = 8 \bmod 6 = 2 $；
• $ s_2 = \text{R} $，因此我们移除最后一个元素，得到数组 $ [1, 4] $；
• $ 1 \cdot 4 \bmod 6 = 4 \bmod 6 = 4 $；
• $ s_3 = \text{R} $，因此我们移除最后一个元素，得到数组 $ [1] $；
• $ 1 \bmod 6 = 1 $；
• $ s_4 = \text{L} $，因此我们移除第一个元素，得到一个空数组。

题目描述

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).

输入格式

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 $ .

输出格式

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.

样例 #1

样例输入 #1

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

样例输出 #1

0 2 4 1 
0 0 0 0 0 
0 0 0 4 4 4 
0

提示

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.

蠢货，从前往后不行，从后往前

const int N = 200010;

int a[N];
int b[N];
int ans[N];
void solve()
{  
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    string s;
    cin >> s;
    int l = 1, r = n;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'L')  b[i] = a[l], l++;
        else b[i] = a[r], r--;
    }
    int top = 1;
    for (int i = n-1; i >=0; i--)
    {
        top = top * b[i] % m;
        ans[i] = top;
    }
    for (int i = 0; i <= n-1; i++) cout << ans[i] << " ";
    cout << '\n';
}