题解

· · 题解

随机跳题随到了，看见题解区还有位，顺手来站个坑。

首先看数据范围，n\le10^6，暴力模拟是 O(n^2) 的，会超时。

观察三种操作：

  3. 不满足上述操作，翻转序列。

对于第一个操作，直接判断即可。

若当前取走的是 i 号球，则 a_{i+1}\gets a_i\times a_{i+1}。

注意 p\le10^{18}，乘起来再模会爆，可以使用 __int128，也可以快速乘。

对于第二个操作，我们可以开一个标记变量，记为 flag，表示颜色是否翻转过。

若 flag=0，第二个操作的条件为 c_1=\texttt{P},c_2=\texttt{G},cnt\equiv1\pmod2；若 flag=1，第二个操作的条件为 c_1=\texttt{G},c_2=\texttt{P},cnt\equiv1\pmod2。

颜色翻转对于第一个操作并没有影响，因为颜色相同的球不管怎么翻转还是颜色相同的。

对于第三个操作，我们可以不翻转数组，类似双指针，直接开两个变量 l,r，再开一个变量 rev，表示是否翻转。

若需要翻转，则从 r 开始向左操作；否则从 l 开始向右操作。

直到 l=r 时跳出循环，再将答案加上 a_l 即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+100;
int n,flag,rev,cnt,l,r;ll mod,ans,a[N];char c[N];//flag 表示颜色是否翻转，cnt 表示操作次数
int main(){
    cin>>n>>mod,l=1,r=n;
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]%=mod;
    scanf("%s",c+1);
    while(l<r){
        cnt++;
        if(rev){//翻转过
            ans=(ans+a[r])%mod;//记录答案 
            if(c[r]==c[r-1])a[r-1]=(__int128)a[r]*a[r-1]%mod;
            else if((cnt&1)&&(!flag&&c[r]=='P'&&c[r-1]=='G'||flag&&c[r]=='G'&&c[r-1]=='P'))flag^=1;//颜色翻转
            else rev^=1;//序列翻转
            a[r--]=0;//被拿走
        }else{//未翻转
            ans=(ans+a[l])%mod;//记录答案
            if(c[l]==c[l+1])a[l+1]=(__int128)a[l]*a[l+1]%mod;
            else if((cnt&1)&&(!flag&&c[l]=='P'&&c[l+1]=='G'||flag&&c[l]=='G'&&c[l+1]=='P'))flag^=1;//颜色翻转
            else rev^=1;//序列翻转
            a[l++]=0;//被拿走
        } 
    }return cout<<(ans+a[l])%mod,0;//最后记得要模
}