jsc2019_qualC Cell Inversion

先吐槽一下这个比赛的奇怪名字

这个破名字让我实在不知道博客标题该叫啥/px

题目大意

给你一个长度为2n的序列

包括W和B

每次可以选一个区间将里面的颜色反转

但是每个点只能被作为端点选一次

问将序列全部变为W的操作方案数

分析

可以将区间左右端点看作左括号与右括号

我们发现对于W一定被偶数个区间覆盖

B一定被奇数个区间覆盖

所以如果当前区间数正好符合则填右括号

否则填左括号改变奇偶性

填每个右括号时匹配的方案数即为剩余左括号数

最终方案乘上排列方案n!即可

代码

#include<bits/stdc++.h>

using namespace std;

const int mod = 1e9+;

char s[];

int n,ans=,num;

int main(){

    int i,j,k;

    scanf("%d",&n);

    scanf("%s",s);

    for(i=;i<*n;i++)

      if(!(((s[i]=='W')^num)&))num++;

        else ans=1ll*ans*num%mod,num--;

    if(num!=){puts("");return ;}

    for(i=;i<=n;i++)ans=1ll*ans*i%mod;

    printf("%d\n",ans);

    return ;

}

巴特西

jsc2019_qualC Cell Inversion

最新文章

热门文章