CF2256D
2026-08-10 08:02:21
发布于：广东
18阅读
0回复
0点赞
比较神秘的题目，@cjdst教我c++，教我交互题
。
遇到求方案数的题目，90%都跟dp或者组合数有关，显然任意次翻转用dp难以处理（？），优先考虑组合数。
观察到限制时才能翻转，换句话说：
1.每次翻转必然不会改变，的数量；
2.每次翻转也必然不改变，连续块的数量。
所以，由上，任意次翻转相当于对，块进行重排。
有了这两个结论，一切都非常简单了，利用隔板法，以为例，令总数为，的初始块数为，相当于从个空位放入个板子，同理，最后就是一个乘法原理，就做完了。
#include <bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
constexpr ll N = 1e6+5, mod = 998244353;
ll fact[N], inv[N];
ll fpow(ll a, ll b) {
ll res = 1;
a %= mod;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
void init() {
// freopen("1.in","r",stdin);
// freopen("my.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
fact[0] = 1;
for (int i = 1; i < N; ++i) fact[i] = fact[i - 1] * i % mod;
inv[N - 1] = fpow(fact[N - 1], mod - 2);
for (int i = N - 2; i >= 1; --i) {
inv[i] = inv[i + 1] * (i + 1) % mod;
}
}
ll C(ll n, ll k) {
if (k > n) return 0;
if (k == 0 || k == n) return 1;
return fact[n] * inv[k] % mod * inv[n - k] % mod;
}
void Main() {
int n;
cin >> n;
string s;
cin >> s;
s = '#' + s;
int c0 = 0, c1 = 0, b0 = 0, b1 = 0;
int cur = s[1] - '0';
if (s[1] == '0') ++c0;
else ++c1;
for (int i = 2; i <= n; ++i) {
if (s[i] == '0') {
++c0;
if (cur == 1) {
++b1;
cur = 0;
}
} else if (s[i] == '1') {
++c1;
if (cur == 0) {
++b0;
cur = 1;
}
}
}
if (cur == 0) ++b0;
else ++b1;
// cout<<c0 << ' ' <<c1 << ' ' <<b0 << ' ' <<b1<<endl;
cout << (b1 > 0 ? C(c0 - 1, b0 - 1) : 1) * (b0 > 0 ? C(c1 - 1, b1 - 1) : 1) % mod << endl;
}
}
int main() {
CZW::init();
int Test = 1;
cin >> Test;
while (Test--)
CZW::Main();
return 0;
}
有帮助，赞一个