jsc2019_qualC Cell Inversion

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

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

题目大意

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

包括W和B

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

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

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

分析

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

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

B一定被奇数个区间覆盖

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

否则填左括号改变奇偶性

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

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

代码

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
char s[200100];
int n,ans=1,num;
int main(){
    int i,j,k;
    scanf("%d",&n);
    scanf("%s",s);
    for(i=0;i<2*n;i++)
      if(!(((s[i]=='W')^num)&1))num++;
        else ans=1ll*ans*num%mod,num--;
    if(num!=0){puts("0");return 0;}
    for(i=1;i<=n;i++)ans=1ll*ans*i%mod;
    printf("%d
",ans);
    return 0;
}