长乐 DAY15

今天是博弈论和期望值，对我来说都不会，所以回去昨天改题了，学了费马小定理来乘法逆元，贴代码

#include
using namespace std;
int n,x,y,mod=998244353,l,r;
long long a[100005],ans=1;
char s[100005];
bool k;
int qmi(int a,int k,int p)
{
    int res=1;
    while(k)
    {
        if(k&1) res=(long long)res*a%p;
        k>>=1;
        a=(long long)a*a%p;
    }
    return res;
}
int main()
{
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    scanf("%d",&n);
    a[0]=a[1]=1;
    scanf("%s",s+1);
    if(s[1]=='0') k=1,x++;
    else y++;
    for(int i=2;i<=n;i++)
    {
        a[i]=a[i-1]*(4*i-2)%mod*qmi(i+1,mod-2,mod)%mod;
        if(s[i]=='0')
        {
            if(k==0)
            {
                ans=ans*a[y]%mod;
                y=0;
                k=1;
            }
            x++;
        }
        if(s[i]=='1')
        {
            if(k==1)
            {
                ans=ans*a[x]%mod;
                x=0;
                k=0;
            }
            y++;
        }
    }
    if(k==1) ans=ans*a[x]%mod;
    else ans=ans*a[y]%mod;
    printf("%lld",ans);
    return 0;
}