9. 【Codeforces Round 927 (Div. 3)】 C. LR-remainders

$$C.LR-remains$$$$每次测试时限：2秒$$$$每次测试的内存限制：256兆字节$$

---

题目描述

给你一个长度为 $n$ 的数组 $a$ 、一个正整数 $m$ 和一串长度为 $n$ 的命令。每条命令要么是字符 “L”，要么是字符 “R”。

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

• 首先，输出数组 $a$ 中所有元素除以 $m$ 后的乘积余数。
• 然后，如果命令为 “L”，则从数组 $a$ 中移除最左边的元素；如果命令为 “R”，则从数组 $a$ 中移除最右边的元素。

注意，每次移动后，数组 $a$ 的长度都会减少 $1$ ，处理完所有命令后，数组 $a$ 将为空。

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

---

输入

第一行包含一个整数 $t$ ( $1\le t\le 10^4$ ) - 输入中测试用例的数量。然后是 $t$ 个测试用例的描述。

输入的每个测试用例由三行组成。

第一行包含两个整数 $n$ 和 $m$ ( $1\le n\le 2\cdot 10^5,1\le m\le 10^4$ ) - 数组的初始长度 $a$ 和余数取值。

第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$ ( $1\le a_i\le 10^4$ ) - 数组 $a$ 的元素。

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

保证测试中所有测试用例的 $n$ 值之和不超过 $2\cdot 10^5$ 。

---

输出

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

---

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
const int N = 200010;

int a[N];

void solve()
{
    int n,m; cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    string s; cin>>s; s='0'+s;
    
    int l=1, r=n;
    for(int i=1;i<=n-1;i++)
        if(s[i]=='L')l++;
        else r--;
    
    vector<int>ans;
    int res=a[l]%m;
    ans.push_back(res);
    for(int i=n-1;i>=1;i--)
    {
        if(s[i]=='L')
        {
            l--;
            res=(res*a[l])%m;
            ans.push_back(res);
        }
        else
        {
            r++;
            res=(res*a[r])%m;
            ans.push_back(res);
        }
    }
    for(int i=n-1;i>=0;i--)cout<<ans[i]<<" ";
    cout<<endl;
}

int main()
{
    int t; cin>>t;
    while(t--)
    {
        solve();
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

解题思路：

因为正着做的话需要进行除法运算，而除法对取模运算不是封闭的，不能随意取模，因此需要使用逆元，但是题目中的m与a[i]并不一定互质，所以无法求出逆元，因此该方法无法使用。

既然正着做不行，那么就试试看倒着做，而倒着做就变成了乘法运算，而乘法对取模运算是封闭的，可以随意取模，因此这道题可以通过倒着做解决

---