CF1545B题解
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;
}