题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$，$mod(1 \leq mod \leq 10^4)$，长为$n$的数组$a(1 \leq a[i] \leq 10^4)$，长为$n$的字符串 $s$，只包含L和R。

从左到右遍历$s$，如果是L，则去掉$a$最左边的元素，否则去掉$a$最右边的元素。每次去掉元素【之前】，输出$a$中所有元素乘积模$m$的结果。

输入样例

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

输出样例

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

算法

逆向思维

这个题乍一看很快就想到用逆元来做，但是码着码着突然发现模数$m$不一定是质数，这也就意味着逆元未必存在，除法不能用逆元的话就比较难办了。

我们不想进行除法操作，那可不可以全部都是乘法操作呢？倒着来做就可以了。令$l=1$，$r=n$，正着遍历$s$串，如果$s[i]=$L，$l$就自增；如果$s[i]=$R，$r$就自减。初始化答案$res=1$，然后倒着遍历$s$，如果$s[i]=$L，$l$就自减，把$a[l]$乘入答案$res$；如果$s[i]=$R，$r$就自增，把$a[r]$乘入答案$res$。每遍历一个索引就把当前的答案$res$存入答案数组$ans$，最后倒着输出答案数组中的元素即可。

复杂度分析

时间复杂度

一共遍历了两遍$s$串，时间复杂度为$O(n)$。

空间复杂度

由于整个过程中是离线处理，所以除了输入的$a$数组和$s$串，还需要一个答案数组来存每次操作的答案，不然最后没有办法倒序输出。因此，额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 200010;
int t, n, mod, a[N];
char s[N];

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &mod);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        scanf("%s", s + 1);
        int l = 1, r = n;
        for(int i = 1; i <= n; i++) {
            if(s[i] == 'L') {
                l++;
            }else {
                r--;
            }
        }
        int res = 1;
        vector<int> ans;
        for(int i = n; i >= 1; i--) {
            if(s[i] == 'L') {
                l--;
                res = 1LL * res * a[l] % mod;
            }else {
                r++;
                res = 1LL * res * a[r] % mod;
            }
            ans.push_back(res);
        }
        for(int i = n - 1; i >= 0; i--) {
            printf("%d ", ans[i]);
        }
        puts("");
    }
    return 0;
}