前言
题目链接：洛谷。
想了一个小时，想到后只用 \(1\) 分钟过了的题。
官方题解过于晦涩，看到一篇很清晰的题解，于是写题解以记之。
终于遇到时间瓶颈在输入的题目。
题意简述
有一个长度为 \(n\) 的 \(\tt 01\) 串 \(S\)，你要对 \(S\) 进行 恰好 \(n\) 次操作。每次操作选择 \(1 \leq l {\color{red}{<}} r \leq n\)，然后按位翻转 \(S_{l\dots r}\)。
求 \(n\) 次操作后，所有可能不同的 \(S\) 的个数模 \(998244353\) 的余数。\(2 \leq n \leq 10^5\)。
题目分析
经过大量模拟，发现在 \(n \geq 4\) 时答案就是 \(2^n\)，于是愉快地过了这题。考虑证明。
发现既然为 \(2^n\)，说明最终能到达所有长为 \(n\) 的 \(\tt 01\) 串，由于操作的可逆性，所有 \(\tt 01\) 串是能够相互转化的。换句话说，和输入的 \(S\) 是没有关系的。自然把问题转移到一个新的 \(\tt 01\) 串 \(T\) 上，其每一位表示 \(S\) 的这一位和最终的串的这一位相等或是不等。要证明答案是 \(2^n\)，说明我们总能从全 \(0\) 串变成任意的 \(T\)。
考虑用归纳法。由于操作长度要 \(\geq 2\)，假设前 \(n - 2\) 已经匹配，我们要用恰好 \(2\) 次操作弄好后两位。现在要做的就是分类讨论这 \(2\) 位可能的 \(4\) 种情况，并构造出对应的操作。为了方便表述，不妨拿出这 \(2\) 位和后面相邻的 \(2\) 位，构成长度为 \(4\) 的子串。
- 形如 \(\tt 00xx\)。
两次操作分别是：\([1, 2]\)，\([1, 2]\)。 - 形如 \(\tt 01xx\)。
两次操作分别是：\([2, 4]\)，\([3, 4]\)。 - 形如 \(\tt 10xx\)。
两次操作分别是：\([1, 4]\)，\([2, 4]\)。 - 形如 \(\tt 11xx\)。
两次操作分别是：\([1, 4]\)，\([3, 4]\)。
要完成以上操作，必要的条件是 \(n \geq 4\)。如果此时没有后两位 \(\tt xx\) 的辅助，我们可以借用前面的两位。
自此，我们证明了结论对于 \(\geq 4\) 的所有偶数是成立的。当 \(n\) 为奇数时，如果最后一位是 \(1\)，就随便翻转 \([k, n]\)，其中 \(k\) 是 \([1, n - 1]\) 里任意一位，先把最后一位满足了，对于前 \(n - 1\) 位再用之前的方法搞好；如果最后一位是 \(0\)，那就浪费一次操作，任选 \(l < r < n\)，翻转 \([l, r]\) 即可。
证明就结束了，十分简单。再用形式化的语言表达答案：
\[ans = \begin{cases} 1 & \text{ if } n=2 \\ 4 & \text{ if } n=3 \\ 2^n & \text{ if } n \geq 4 \end{cases} \]算法时间复杂度为 \(\Theta(\log n)\)，但是输入有瓶颈，是 \(\Theta(n)\) 的。
代码
t = int(input())
while t:
n = int(input())
input()
if n == 2:
print(1)
elif n == 3:
print(4)
else:
print((1 << n) % 998244353)
t -= 1
以及：
for _ in range(int(input())):n=int(input());input();print({2:1,3:4}[n]if n<=3 else(1<<n)%998244353)