题意：
给你一个01串$str$，需要将$1-2n$分成两个大小为n的集合$A$和$B$，求有多少种划分方案使得这两个集合满足：
1.对于任意$1<i<n$，都有$A_{i-1}<A_{i}<A_{i+1}$和$B_{i-1}<B_{i}<B_{i+1}$
2.对于任意$1\leq i \leq n$，若$str_{i}==0$，则$A_{i}>B_{i}$；否则$A_{i}<B_{i}$
$n\leq 10^5$
题解：
如题。
首先我们可以将数从小往大考虑并秒出一个dp，状态为$dp(i,j)$表示A串填了i个，B串填了j个的方案数。
但无法通过$1e5$的数据。我们需要观察题目的性质。
画个图来表示合法的情况，大概就是这样的：
这时我们可以发现，若存在这样的一个结构：
那么整个序列实际上被分成了两部分：在第二列及之前的部分和在第三列及之后的部分。
且这两部分满足前一部分的任意元素小于后一部分的任意元素。
于是我们可以发现，整个序列被若干个这样的结构分成了若干段，且每段的值域是确定的。
注意到这样的结构只会在一段连续的0与一段连续的1之间出现。
那么只需要考虑一段长度为k的连续0(1)对答案的贡献是多少，最后将贡献相乘即可。
假如这段全部由0组成，那么一个填法合法当且仅当在从小往大填的过程中，A的个数永远小于等于B的个数。
如果我们将A视作右括号，B视作左括号，那么实际上就是求合法的括号序列的个数。
长度为n的合法括号序列的个数是啥？卡特兰数啊！即为$\frac{C_{2n}^{n}}{n+1}$
于是$O(nlogn)$解决即可。
然而我并没有A这题而是A了t2，可以退役了。
代码：
#include<bits/stdc++.h> #define maxn 500005 #define maxm 500005 #define mod 998244353 #define inf 0x7fffffff #define ll long long using namespace std; ll N,jc[maxn],inv_jc[maxn],inv[maxn]; char str[maxn]; inline ll read(){ ll x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline ll power(ll a,ll b){ ll ans=1; while(b){ if(b&1) ans=ans*a%mod; a=a*a%mod,b>>=1; } return ans; } inline void init(){ jc[0]=1,inv_jc[0]=1; for(ll i=1;i<=N*2;i++) jc[i]=jc[i-1]*i%mod,inv_jc[i]=power(jc[i],mod-2); for(ll i=1;i<=N+1;i++) inv[i]=power(i,mod-2); } inline ll C(ll n,ll m){return jc[n]*inv_jc[n-m]%mod*inv_jc[m]%mod;} int main(){ N=read(),cin>>str+1,init(); ll ans=1; for(ll i=1;i<=N;){ ll j=i; while(j<=N && str[j]==str[j+1]) j++; ll len=j-i+1; i=j+1; ans=ans*C(2*len,len)%mod*inv[len+1]%mod; } printf("%lld\n",ans); return 0; }