同步发布于 here。
不知道打表找规律能不能过。
注意，这是一篇打表找规律猜结论的题解，如果你想看严谨证明请移步别的题解。
神秘诈骗题。
题意
多次询问。
每次给定一个长为 \(2^n-1\) 的环，环上第 \(i\) 个数为 \(i\)。
现在将每个数与当前这个状态的下一个数求异或，问循环节的最小长度 \(\mod 998244353\) 的结果。
令询问次数为 \(t\)，则 \(n \le 10^9,t \le 5 \times 10^5\)。
思路
其实没思路。
以下定义 \(\bigoplus\) 为异或符号。
考虑到异或是具有自反性的，也就是 \(a \bigoplus a = 0\)，所以形成一个环一定是通过自反性得来的。
然后我们又需要知道，对于一个数 \(x\)，其也可以由 \((\bigoplus_{i=1}^{2^n-1} i) \oplus x\) 得到，其中需要满足的是 \(n \ge 2\)，这是因为异或的经典结论，即：
当 \(n \ge 2\) 时，\(\bigoplus_{i=1}^{2^n-1} i = 0\)，因为 \(2^n-1 \equiv 3 \pmod 4\)。
那我们也就能看成 \(\bigoplus_{i=1,i \neq x}^{2^n-1} i = x\)。
我当时并没有想到后面怎么推，于是我想到了手动模拟找规律。
我们先来看样例对于 \(n=2\) 时候的模拟情况。
原数：\(1,2,3\)，那么有以下转化。
最后一步正好是我们上面说的 \(\bigoplus_{i=1,i \neq x}^{2^n-1} i = x\)。
此时循环节长度为 \(3\)。
再看看 \(n=3\)。
原数即 \(1,2,3,4,5,6,7\)，则有：
可以发现再来一步我们就能凑成 \(\bigoplus_{i=1,i \neq x}^{2^n-1} i = x\) 的形式了，太长了就不写了。
这个循环节长度为 \(7\)。
可以发现什么？对于 \(n = 2,n = 3\) 时的循环节长度为 \(2^n-1\)，所以我们大胆猜测对于 \(n \ge 2\) 其循环节长度为 \(2^n - 1\)，写出代码取模来发现样例确实如此。
将 \(n=1\) 特判即可。
using ll = long long;
constexpr int mod = 998244353;
ll t, n, m;
ll qpow(ll x, ll y)
{ll res = 1;while(y){if(y & 1) res *= x, res %= mod;x *= x;x %= mod;y >>= 1;}return res;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> t;while(t --){cin >> n;if(n == 1) cout << "NO\n";else cout << (qpow(2, n) - 1 + mod) % mod << '\n';//这个我是怕取模后 - 1 小于 0 了}return 0;
}