Codeforces Round ＃732 (Div. 2) D. AquaMoon and Chess

First, let's consider the simpler case
$1100000000000$
hold $11$ As a group , This group can move on the number axis , The situation of each group corresponds to one $state$
Extension , For a continuous string of odd length
$000011111000000$
You can know that there is $len/2$ A mass of , When the number of the left and right groups of this continuous string is determined, this group leaves “1” The location is uniquely determined , Take the example above , You can know that if the two regiments are on the left, what remains is the rightmost $1$, One on the left and one on the right are left in the middle $1$……

Back to the topic , We find all the cliques in a string , Then the conclusion drawn from the above , When the position of the regiment is determined, it is left alone “1” Determine the location , So we only need to consider the position relationship of the Group .
The problem turns into $1\ast m$ Space for $n$ individual $1\ast 2$ Number of options for items . Just write a formula .

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353;
ll poww(ll a,ll b)
{
    
    ll t=1;
    while(b>1)
    {
    
        if(b%2==1)t=t*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return t*a%mod;
}
ll poww1[100005],poww2[100005];
void init()
{
    
    poww1[0]=1;
    poww2[0]=1;
    for(int i=1;i<=100000;i++)poww1[i]=poww1[i-1]*i%mod;
    for(int i=1;i<=100000;i++)poww2[i]=poww2[i-1]*poww(i,mod-2)%mod;
// printf("%lld\n",poww2[3]);

}
char s[100005];
int main()
{
    
    init();
    int t;
    scanf("%d",&t);
    while(t--)
    {
    
        int n;
        scanf("%d",&n);
        scanf("%s",s+1);
        int cnt0=0,cnt=0,cnt2=0;

        for(int i=1;i<=n;i++)
        {
    
            if(s[i]=='0')cnt0++;
            if(s[i]=='1')cnt++;
            if(s[i]=='0')
            {
    
                cnt2+=cnt/2;
                cnt=0;
            }
        }
        cnt2+=cnt/2;
        printf("%lld\n",poww1[cnt0+cnt2]*poww2[cnt0]%mod*poww2[cnt2]%mod);

    }
    return 0;
}