组合数学

B. AquaMoon and Chess

Problem - 1545B - Codeforces

题意：给定一个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;
	}
}