P10877 「KDOI-07」n1gr tS0i

个人认为这道题没有黄的难度。

思路

我先看了 $n=30$ 的样例，有一个猜想是答案是 $2^n$，然后用计算器算了一下 $n=30$ 的这个数据发现猜想是对的。

但是如果 $n=2$ 的情况发现不是这样的，所以又猜测只有当 $n$ 大于一个界限的时候才是 $2^n$。

首先，$n = 2$ 的情况样例已经给了，答案是 $1$，因为这个长度的 $01$ 串只有可能操作 $1$ 次，所以只有可能有 $1$ 种答案。

当 $n = 3$ 的时候，答案只有可能是操作这几个区间：$[1.2]$，$[2,3]$，$[1,3]$ 或者操作这三次 $[1,2],[2,3],[1,3]$。也就是说答案是 $4$。

当 $n \geq 4$，那么我们发现可以对这个串的每一位都进行组合的翻转。就拿 $n = 4$ 的情况来举例，比如说我们要翻转第 $1$ 个数字，那么我们可以先翻转 $[1,3]$，然后再翻转 $[2,3]$ 来把之前对 $[2,3]$ 多余的翻转给转回来，这样做的效果就是翻转 $[1,1]$。

可以发现，对于所有 $n \geq 4$ 的，我们可以通过上述操作翻转 $S$ 的每一位，那么答案就是 $2^n$，这些情况可以用快速幂都解决，注意由于 $n$ 有时候过于大所以不能用预处理。

代码

#include <bits/stdc++.h>

using namespace std;
/*
*/
#define ll unsigned long long
ll p(ll a, ll b, ll q) {
    ll res = 1;
    while (b) {
        if (b & 1) res = (res * a) % q;
        a = (a * a) % q;
        b >>= 1;
    }
    return res % q;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T --) {
        int n; string s; cin >> n >> s;
        if (n == 2) cout << "1\n";
        else if (n == 3) cout << "4\n";
        else cout << p(2, n, 998244353) << "\n";
    }
    return 0;
}