正睿OJ 比大小（卡特兰数或钩子公式）

满分做法：

由题，0和1的交界处把0,1分成两个矩阵，满足杨氏矩阵的性质，可以用钩子公式解决。对于给定形状，不同的杨氏矩阵的个数为：n！除以每个格子的钩子长度加1的积。其中钩子长度定义为该格子右边的格子数和它上边的格子数之和。

因为可以分开算，由打表可知一段的方案数就是长度的卡特兰数。

钩子公式

#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int maxm=2e5+7;
const int mo=998244353;
int n;
char s[maxm];
ll inv[maxm];
ll sum[maxm];
ll ans=1;
ll qpow(ll a,ll b)
{
 ll ans=1,base=a;
 while(b)
 {
  if(b&1)
  ans=ans*base%mo;
  base=base*base%mo;
  b>>=1;
 }
 return ans;
}
int main()
{
 scanf("%d",&n);
 inv[0]=1;
 for(int i=1;i<=2*n;i++)
 inv[i]=inv[i-1]*i%mo;
 sum[1]=2;
 for(int i=2;i<=n;i++)
 sum[i]=sum[i-1]*i*(i+1)%mo;
 scanf("%s",s+1);
 int cnt=1;
 for(int i=2;i<=n;i++)
 {
  if(s[i]!=s[i-1])
  {
    ans=ans*inv[2*cnt]%mo*qpow(sum[cnt],mo-2)%mo;
    cnt=1;
  }
  else cnt++;
 }
 ans=ans*inv[2*cnt]%mo*qpow(sum[cnt],mo-2)%mo;
 printf("%lld\n",ans);
 return 0;
}

卡特兰数

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<set>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
const int mo = 998244353;
int n,cnt;
ll fc[210001],ans = 1;
char s[101000];
ll qp(ll a,ll b){
    ll ans = 1,base = a;
    while(b != 0){
        if(b & 1)ans = ans * base %mo;
        base = base * base %mo;
        b >>= 1;
    }
    return ans;
}
ll cat(int n){
    return fc[2*n]*qp(fc[n],mo-2)%mo*qp(fc[n],mo-2)%mo*qp(n+1,mo-2)%mo;
}
int main()
{
    scanf("%d",&n);
    fc[0] = 1;
    for(int i = 1;i <= 2*n;i ++)
    fc[i] = fc[i-1]*i%mo;
    scanf("%s",s + 1);
    for(int i = 1;i <= n ;i ++){
        if(s[i] == s[i+1]){
            cnt ++;
        }
        else {
            cnt ++;
            ans = ans * cat(cnt)%mo;
            cnt = 0;
        }
    }
    cout<<ans<<endl;
    return 0;
}