AquaMoon and Chess_CodeForces - 1545B

由110变成011，由011变成110，“11”的组合和0可以交换位置

如果是1110 或者是 1110 的情况，红色的“11”与0换位置，变成1011，可以看成蓝色的“11”到了0的后面，蓝色“11”和0的相对位置改变了，而第三个“1”是被动的，他起到了完成蓝色“11”和0换相对位置的桥梁的作用

因此，单独的“1”起到了交换“11”和“0”的桥梁作用，其自身是被动的

比如1100010，等到“11”换到这个情况：0001110 的时候，红色的1让“11”可以与最后一个0交换相对位置

那结果就是C(a+b,a) a是"11"组合的个数，b是0的个数

#include<bits/stdc++.h>
using namespace std;
using ll=long long ;const ll maxn=1e5+5,N=1e5,mod=998244353;
ll fact[maxn],inv[maxn],vis[maxn];ll bin_pow(ll a,ll n){ll res=1;a=a%mod;while(n){if(n&1) res=res*a%mod;a=a*a%mod;n>>=1;}return res;
}ll com(ll n,ll m){if(m>n || m<0) return 0;if(n==m || m==0) return 1;ll ans=fact[n]*inv[m]%mod*inv[n-m]%mod;return ans;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);freopen("D:\\in.txt","r",stdin);//预处理1到1e5的阶乘和逆元fact[0]=1;for(ll i=1;i<=N;i++){fact[i]=fact[i-1]*i%mod;inv[i]=bin_pow(fact[i],mod-2);}ll kase=0;ll T;cin>>T;while(T--){kase++;ll n;cin>>n;string s;cin>>s;ll a=0,b=0;for(ll i=0;i<s.size();i++){if(s[i]=='0') a++;else if(s[i]=='1' && i>0) {if(s[i-1]=='1' && vis[i-1]!=kase){vis[i]=vis[i-1]=kase;b++;}}}//printf("a=%lld b=%lld\n",a,b);cout<<com(a+b,a)<<"\n";}return 0;
}