Codeforces Round 927 (Div. 3) LR-remainders的题解

原题描述：

C.LR-remains

每次测试时限：2 秒

每次测试的内存限制：256 兆字节

输入：标准输入

输出：标准输出

 

样例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 

主题思路：

你想直接模拟，以为乘积最多2e5*1e4=2e9，但我告诉你，乘积最多是1e4^2e5，连__int128都存不下呢！！！

你用了高精度+模拟，的确不会爆，但我告诉你，会超时！！！

于是只能这么做，因为你知道删除的顺序，可以反过来，一开始数组为空，L就是插入a[head]，接着head++,反之，R就是插入a[tail],tail--

用个vector来存储以上插入顺序，接着从后到前枚举（因为你要知道，你是倒着来）

用个x来模拟，每次x*tmp[i](tmp就是用来存插入顺序的vector）

接着x%=m

最后，ans[i] = x;

因为你的数组下标是从后到前枚举的，所以，你要从前到后输出。

知道这些后，是不是就好写很多了呢？

代码Code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
string s;
int a[200010];
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cin>>t;while(t--){int n;long long m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];//读入}int tou=1,wei=n;cin>>s;vector<int> tmp;for(int i=0;i<n;i++){if(s[i] == 'L'){tmp.push_back(a[tou]);tou++;}else{tmp.push_back(a[wei]);wei--;}}//初始化顺序long long x=1;vector<int> ans(n+10);//用x模拟和用ans来存储for(int i=n-1;i>=0;i--){x*=tmp[i];x%=m;ans[i] = x;}for(int i=0;i<n;i++){cout<<ans[i]<<' ';//输出}cout<<'\n';}return 0;
}