CF1545B题解

题目描述

你有一个长为 \(n\) 的棋盘,这个棋盘上有一些棋子,你可以进行如下操作:

如果第 \(i + 2\) 个位置是空的,且第 \(i + 1\) 个位置非空,则可以将第 \(i\) 个位置的棋子挪到第 \(i + 2\) 个位置 (\(i + 2 \leq n\)).

如果第 \(i - 2\) 个位置是空的,且第 \(i - 1\) 个位置非空,则可以将第 \(i\) 个位置的棋子挪到第 \(i - 2\) 个位置 (\(i - 2 \geq 1\)).

现在将给出一个棋盘的初始状态,求可以通过上述操作可以到达的状态数,你可以进行任意次操作,答案对 \(998244353\) 取模.

题解

模拟样例，很容易发现棋子是两两一组进行移动的。我们考虑在没有落单的棋子时我们怎么做这道题，显然我们可以用组合数学插板法解决。

接着，我们来考虑落单的棋子，我们观察发现，落单棋子，要么不动，要么被推着走，所以，成对棋子的移动，完全决定了落单棋子的移动，我们直接删除他们即可。

我们设空格的数量为 \(num1\)，成对棋子的对数为 \(num2\)。答案即为 \(C(num1+num2,num2)\)。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
const int N=2e5+100;
int t,n,inv[N],qinv[N],qz[N];
string s;
int qpow(int a,int b)
{
	int s=1,base=a;
	while(b!=0)
	{
		if(b&1==1)
		{
			s*=base;
			s%=mod;
		}
		base*=base;
		base%=mod;
		b>>=1;
	}
	return s;
}
void pre()
{
	for(int i=1;i<=N-100;i++)
	{
		inv[i]=qpow(i,mod-2);
	}
	qinv[0]=1;
	for(int i=1;i<=N-100;i++)
	{
		qinv[i]=qinv[i-1]*inv[i];
		qinv[i]%=mod; 
	}
	qz[0]=1;
	for(int i=1;i<=N-100;i++)
	{
		qz[i]=qz[i-1]*i;
		qz[i]%=mod;
	}
	return;
}
void C(int a,int b)
{
	cout<<((qz[a]*qinv[a-b])%mod*qinv[b])%mod<<endl;
	return;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	pre();
	cin>>t;
	while(t--)
	{
		cin>>n>>s;
		s=" "+s;
		int num1=0,num2=0;
		bool f=1;
		for(int i=1;i<=n;i++)
		{
			if(s[i]=='0')
			{
				f=1;
				num1++;	
			}
			else
			{
				f^=1;
				num2+=f;
			}
		}
		C(num1+num2,num2);
	}
	return 0;
}