C. LR-remainders

题目描述：C. LR-remainders

解题思路

该题有很多种思维误区，如下：

1、预先将所有数字相乘会超出数据范围，可能会使用高精度，但由于运算操作占据复杂度，会超时
2、如果通过模运算乘法预处理整体，每次去掉一个数可以看作整体在模意义下除以该数，可能会通过乘法逆元转换成模乘法，但题目条件并不能满足求逆元的要求(不满足 $gcd(a, m) = 1$)
3、如果使用唯一分解定理来找规律，找到规律再按规律还原，由于有分解质因数和相乘组合这两个操作，复杂度也较高，会超时
解题思路

1、事实上，不妨逆向来想，既然知道删除顺序，那就可以反向模拟用乘法还原：按照删除顺序，依次记录下按照顺序删除的元素是什么(参照题目第 3 组样例，其存储 $\{ 6,1,2, 3, 5, 4 \}$)，这里可以用栈存储(方便反向还原时使用，此时栈顶为最后一个删除的元素，栈第二个元素为倒数第二个删除的元素)
2、从栈顶依次取出删除的元素，通过模乘法模拟还原回去。此时还原栈顶元素得到的答案即为输出的最后一个答案，还原栈第二个元素得到的答案即为输出的倒数第二个答案。同样用栈存储答案，这样便逆序输出答案

代码实现

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int a[N];

void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    stack<int> stk; // 按删除顺序存储删除的元素
    int L = 1, R = n;
    while (n--)
    {
        char opt;
        cin >> opt;

        if (opt == 'L')
            stk.push(a[L++]);
        else
            stk.push(a[R--]);
    }

    stack<int> ans; // 存储答案
    int now = 1;
    while (stk.size())
    {
        int x = stk.top();
        stk.pop();

        now = now * x % m; // 用模乘法还原
        ans.push(now);
    }

    while (ans.size())
    {
        cout << ans.top() << ' ';
        ans.pop();
    }
    cout << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

题目描述：C. LR-remainders

解题思路

代码实现

页底评论