原题链接``
思路：
显然如果有连续偶数个“1”,那么这些一可以拆成若干组“11”*移动。
因此有了思考方向，用捆绑法，以2个“1”一组。
那么，如果有连续奇数个“1”该怎么办？
经过操作观察，我们发现，多出来的“1”我们其不需要理它，去掉一个“1”将剩下的偶数个“1”按上述分组，将这些组和0排列后，原来多处来的一个“1”是唯一确定的
因此。我们记录0的个数cnt0，记录组数g
答案为从cnt0 + g 个数中 取出g个数的方案数
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 998244353;
ll t;
ll n;
ll cnt0;
ll cnt1;
ll g;
ll ans;
string s;
ll f[100010];
ll fin[100010];
ll qpow(ll x, ll y) {
ll ret = 1ll;
while (y) {
if (y & 1) ret = (ret * x) % mod;
x = (x * x) % mod;
y >>= 1;
}
return ret % mod;
}
ll inv(ll x) {
return qpow(x, mod - 2);
}
void init() {
f[0] = fin[0] = 1ll;
for (ll i = 1; i <= 100000; i++) {
f[i] = (i * f[i - 1]) % mod;
fin[i] = (fin[i - 1] * inv(i)) % mod;
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
init();
cin >> t;
while (t--) {
cnt0 = cnt1 = g = 0;
cin >> n;
cin >> s;
for (int i = 0; i < s.length(); i++) {
if (s[i] == ‘1‘) {
if (i == s.length() - 1) {
cnt1 ++;
g += cnt1 / 2;
}
else {
cnt1 ++;
}
}
else {
cnt0 ++;
g += cnt1 / 2;
cnt1 = 0;
}
}
ans = ((f[cnt0 + g] * fin[g]) % mod * fin[cnt0]) % mod;
cout << ans << "\n";
}
return 0;
}