B. AquaMoon and Chess
题意：给定一个1*n的方格，有些方格有棋子，每个棋子可以这样移动：
1，当i,i+1有棋子且i+2<=n时，可以将i移动到i+2的位置。
2，当i,i-1有棋子且i-2>0，可以将i移动到i-2位置上。
给定初始棋子分布，问有多少中可能到达的情形。
n<=1e5
题解：什么样的棋子才能移动？我们发现如果一个棋子与另一个棋子成对，那么可以遍历整个空间。
如果有落单棋子，那么其不能动。分组难以统一，我们想把其先变成全部在一侧的情形再进行考虑。我们发现将所有可以移动的棋子全部移到最左边后，出现了形如1111110001000100101000情况，这时分组唯一确定，即最左边开始两两一组。若我们视两个组成一组，则我们认为1组的移动为整体向右平移一位，且我们发现若将 011100->01110我们可以认为是跨过了单独的1。若设单独的棋子有l个，组有x个，这样我们便可以将问题等价为求n-l-x个位置中选x个位置有多少种方法，结果显然。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,mod=998244353;
int a[N];
int fac[N],finv[N];
int qpow(int x,int y){
int ans=1;
while(y){
if(y&1) ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
int C(int n,int k){
if(n<k) return 0;
if(n==0) return 0;
return fac[n]*finv[n-k]%mod*finv[k]%mod;
}
signed main(){
int w=2e5;
fac[0]=1;
for(int i=1;i<=w;i++){
fac[i]=fac[i-1]*i%mod;
}
finv[1]=1;
for(int i=2;i<=w;i++) finv[i]=qpow(fac[i],mod-2);
int T;cin>>T;
while(T--){
int cnt=0,x=0,l=0;
int n;cin>>n;
string s;cin>>s;
for(int i=1;i<=n;i++) a[i]=s[i-1]-'0';
for(int i=1;i<=n;i++){
if(a[i]==0){
if(cnt%2) cnt--,l++;
x+=cnt/2;
cnt=0;
}
else cnt++;
}
if(cnt){
if(cnt%2) cnt--,l++;
x+=cnt/2;
}
int ans=1;
ans=max(ans,C(n-x-l,x));
cout<<ans<<endl;
}
}