题目翻译 link
有 \(N\) 人围坐在一张圆桌旁，按逆时针顺序编号为 \(1\) 至 \(N\) 。每个人都有一个惯用手
圆桌上有 \(N\) 把勺子，编号为 \(1\) 到 \(N\) ，每对相邻的人之间放一把勺子
给你一个 \((1, \dots, N)\) 的排列组合 \((P_1, \dots, P_N)\) 。在 \(i=1,\dots,N\) 的顺序中，人 \(P_i\) 的行为如下：
- 如果两边都有剩余的勺子，他们会拿自己惯用手一边的勺子
- 如果左侧或右侧有剩余的勺子，他们将拿走其中一个
- 否则，他们什么也不会做
给出了一个长度为 \(N\) 的字符串 \(S\) ，由 L、R 和 ?组成：
- 如果 \(S_i\) 是 "L"，那么 \(i\) 是左撇子
- 如果 \(S_i\) 是 "R"，那么 \(i\) 是右撇子
在 \(2^N\) 个可能的主手组合中，找出有多少个满足以下所有条件的 \(s\)，模数为 \(998244353\) ：
当每个人都行动完后，每个人都拿了一把勺子
方法
法一
暴力枚举每种可能的 \(s\) ，然后检验
时间复杂度 \(O_{(2^X \times N)}\) ， \(X\) 为 ? 的个数
法二
分析
我们可以发现对于一个满足条件的 \(S\) ，每个人都应该拿与第一个拿的人同侧的勺子
于是：
我们可以分类讨论：
讨论第一个拿的人是拿左边还是右边：
- 若为
R只讨论右边 L只讨论左边?讨论两种最后求和
每个人拿的方向应与第一个拿的人一致，然后找规律
规律
（注：这里类似 “ \(P_i\) 为 L ” 的语句其实是 “ \(S[P_i]\) 为 L ” ，为了简便记作 \(P_i\) ）
若第一个拿的人拿左边
对于第 \(P_i\) 个人来说
- 如果他右边的人 \(r\) 已经先拿过他左边的勺子，那么 \(P_i\) 可以为
L或R，那么 \(ans\) 乘 \(2\) (注意，若 \(P_i\) 确定， \(ans\) 不变）- 如果他右边的人 \(r\) 后拿，那么他只能拿左边的勺子， \(ans\) 不变
- 如果他右边的人 \(r\) 没有先拿过他左边的勺子且 \(P_i=\)
R，那么第一个拿的人拿左边的情况误解，即 \(ans=0\)
若第一个拿的人拿右边，可类似若第一个拿的人拿左边推出
这里为了简短就不写啦
注意取模！！！你猜我怎么知道的 警示后人
代码实现：
#include<bits/stdc++.h>
#define put(n) scanf("%lld",&n)
#define out(n) printf("%lld\n",n)
#define int long long
#define fd(i,a,b) for(int i=a;i<=b;i=-~i)
using namespace std;
int n,p[1000100],f[1000100],mod=998244353;
//f记录第i个人第几个拿
char s[1000100];
int ans1=1,ans2=1;// 拿左边 拿右边
signed main()
{
put(n);
fd(i,1,n) put(p[i]),f[p[i]]=i;
fd(i,1,n) cin>>s[i];
//第一个拿的人拿左边
fd(i,1,n)
{
int r=p[i]+1;//r 当前拿的人右边的人的编号
if(r==n+1) r=1;//小坑
if(s[p[i]]=='?')
{
if(f[r]<i) ans1*=2;
ans1%=mod;
}
else if(s[p[i]]=='R')
{
if(f[r]>i)
{
i=n+1;
ans1=0;
break;
}
}
}
//第一个拿的人拿右边
fd(i,1,n)
{
int l=p[i]-1;//l 当前拿的人左边的人的编号
if(l==0) l=n;//小坑
if(s[p[i]]=='?')
{
if(f[l]<i) ans2*=2;
ans2%=mod;
}
else if(s[p[i]]=='L')
{
if(f[l]>i)
{
i=n+1;
ans2=0;
break;
}
}
}
if(s[p[1]]=='R') out(ans2);
else if(s[p[1]]=='L') out(ans1);
else out((ans1+ans2)%mod);//如果Pi为?那么算两种情况之和
return 0;
}
无关的话（审核大大，求过审）：被禁言了，怎么解啊？
感谢观看
标签：右边,第一个,左边,Taking,arc175,题解,define,勺子,out From： https://www.cnblogs.com/whrwlx/p/18094188