本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-25 08:20:35

题意

在一个环上有 $N$ 个人，每两人之间有一把勺子，所有人按照 $P$ 排列顺序操作。一人操作时若左右都有勺子，则拿自己惯用手那边的；若只有一边有勺子，则直接拿；若无勺子则不操作。

给定 $P$ 和某些人的惯用手，求能使所有人都拿到勺子的惯用手方案数。

思路

如果把这个环画出来，环上就是一个人一个勺子交叉，如此重复 $N$ 组。

模拟一下就会发现，若某两人选择勺子的方向不同，则他们之间剩下的勺子数与人数之和为奇数，这样一定不合法。

所以我们得到，合法的取法只有两种，即所有人都取自己左手边的勺子，或所有人都取自己右手边的勺子。

那么只需要模拟取两次，每次都直接钦定每个人所拿的勺子，再按 $P$ 的顺序依次处理。

处理时，若不拿的另一把勺子还在，就必须确定惯用手以拿到指定的那把，此时若与 $S$ 中给出的信息冲突则无解；若另一把已经不在了，那么惯用手任意，此时若给出信息为问号则方案数乘 $2$。

此处不需要考虑自己要拿的勺子是否已被取走，因为每个人都只会取自己对应的那把勺子，不会出现拿别人勺子的情况。

最后把两种取法对应的方案数相加即可。

代码

#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=2e5+10;
const int mod=998244353;
int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
    return s*w;
}
int n,sa=1,sb=1,p[N]; 
char s[N];
bool v[N];\/\/勺子是否被取走 
signed main()
{
	n=read();
	for(int i=1;i<=n;i++) p[i]=read();
	cin>>s;
	for(int i=1;i<=n;i++)\/\/所有人都取左手边的 
	{
		if(v[(p[i]%n)+1]) \/\/若另一把已被取走，则惯用手任意 
		{
			if(s[p[i]-1]=='?') sa=(sa*2)%mod;\/\/若是问号则乘2 
		}
		else if(s[p[i]-1]=='R') \/\/另一把未被取走，则需确定惯用手 
		{
			sa=0;
			break;
		}\/\/此时若与给定信息冲突则无解 
		v[p[i]]=1;\/\/标记已取走 
	}
	memset(v,0,sizeof(v));
	for(int i=1;i<=n;i++)\/\/都取右手边的，同上 
	{
		if(v[p[i]]) 
		{
			if(s[p[i]-1]=='?') sb=(sb*2)%mod;
		} 
		else if(s[p[i]-1]=='L')
		{
			sb=0;
			break;
		}
		v[(p[i]%n)+1]=1;
	}
	cout<<(sa+sb)%mod;
	return 0;
}