题意
给你一个长度为 \(n\) 的 \(0/1\) 串 ，每次你可以选择一段端点相同的区间，将区间内顺序反转
解法
我们将序列抽象为 \(x_1\) 个 1 ，\(x_2\) 个 0 ，\(x_3\) 个 1，...... ，$ x_k$ 个 \(0\) ( \(x_1\) 和 \(x_k\) 可能为 \(0\) )，
我们发现操作的实质是改变 \(x\) ,但不改变 \(1/0\) 的相对顺序，所以我们可以钦定只能对 \(101\) 和 \(010\) 操作
这是和原操作等效的，所以题就变为对于\(0/1\) 有 \(p\) 个 \(0/1\) ，有 \(q\) 个 盒子，每个盒子不能为空，求数量
这就很简单，正常用插板法就行
#include<bits/stdc++.h>
using namespace std;#define int long longconst int N=1e6+10;
const int M=2e6+10;
const int mod=998244353;int n;
char s[N];int jc[M],pv[M];int qp(int a,int b){int res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod; b>>=1;}return res;}void init(){jc[0]=1;for(int i=1;i<M;i++) jc[i]=jc[i-1]*i%mod;pv[M-1]=qp(jc[M-1],mod-2);for(int i=M-1;i>=1;i--) pv[i-1]=pv[i]*i%mod; }int C(int n,int m){if(n<m||n<0||m<0) return 0;return jc[n]*pv[m]%mod*pv[n-m]%mod;}int num[2],cnt[2];void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>s[i];num[1]=num[0]=cnt[1]=cnt[0]=0;for(int i=1;i<=n;){int r=i;while(r+1<=n&&s[r+1]==s[i]) r++;cnt[s[i]-'0']++; num[s[i]-'0']+=r-i+1;i=r+1;}cout<<max(1ll,C(num[0]-1,cnt[0]-1))*max(1ll,C(num[1]-1,cnt[1]-1))%mod<<'\n';}signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);init();int T; cin>>T;while(T--) solve();}