自动搬运

查看原文

来自洛谷，原作者为

	mlvx 喵

搬运于2025-08-24 22:13:13，当前版本为作者最后更新于2024-03-28 15:30:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

观察三种操作：

1. $c_1=c_2$，合并两个球。

2. $c_1=\texttt{P},c_2=\texttt{G},cnt\equiv1\pmod2$，将颜色翻转。

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;//最后记得要模
}