ARC175A 题解

KSCD_ · 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;
}