[ARC146C] Even XOR
题意翻译
## 题面
请输出满足下述条件的集合 $S \in \{0,1,2,\ldots,2^N-1\}$ 的个数对 $998244353$ 取模后的结果。
- 对于所有 $S$ 的非空子集 $T$,均满足下列条件之一:
- $\lvert T \rvert$ 为奇数;
- $T$中所有元素的异或和不为 $0$。
[何为异或?](https://oi-wiki.org/math/bit/#%E4%B8%8E%E6%88%96%E5%BC%82%E6%88%96)
## 输入
一行一个整数 $N$。
## 输出
一行一个整数,表示答案对 $998244353$ 取模后的结果。
## 数据范围&限制
$1 \le N \le 2 \times 10^5$,保证输入数据全为整数。
题目描述
[problemUrl]: https://atcoder.jp/contests/arc146/tasks/arc146_c
$ 0 $ 以上 $ 2^N $ 未満の非負整数からなる集合 $ S $ のうち、以下の条件を満たすものの個数を $ 998244353 $ で割ったあまりを出力してください。
- $ S $ の空でない部分集合 $ T $ は以下のどちらかを満たす。
- $ T $ の要素数が奇数
- $ T $ の全要素の $ \mathrm{XOR} $ が $ 0 $ でない
$ \mathrm{XOR} $ とは 非負整数 $ A,\ B $ のビット単位 $ \mathrm{XOR} $ 、$ A\ \oplus\ B $ は、以下のように定義されます。
- $ A\ \oplus\ B $ を二進表記した際の $ 2^k $ ($ k\ \geq\ 0 $) の位の数は、$ A,\ B $ を二進表記した際の $ 2^k $ の位の数のうち一方のみが $ 1 $ であれば $ 1 $、そうでなければ $ 0 $ である。
例えば、$ 3\ \oplus\ 5\ =\ 6 $ となります (二進表記すると: $ 011\ \oplus\ 101\ =\ 110 $)。
一般に $ k $ 個の整数 $ p_1,\ p_2,\ p_3,\ \dots,\ p_k $ のビット単位 $ \mathrm{XOR} $ は $ (\dots\ ((p_1\ \oplus\ p_2)\ \oplus\ p_3)\ \oplus\ \dots\ \oplus\ p_k) $ と定義され、これは $ p_1,\ p_2,\ p_3,\ \dots\ p_k $ の順番によらないことが証明できます。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $
输出格式
答えを出力せよ。
输入输出样例
输入样例 #1
2
输出样例 #1
15
输入样例 #2
146
输出样例 #2
743874490
说明
### 制約
- $ 1\ \le\ N\ \le\ 2\ \times\ 10^5 $
- 入力は全て整数である。
### Sample Explanation 1
$ \lbrace\ 0,2,3\ \rbrace $ や $ \lbrace\ 1\ \rbrace $ や $ \lbrace\ \rbrace $ は条件を満たします。 $ \lbrace\ 0,1,2,3\ \rbrace $ は条件を満たしません。 なぜなら、$ \lbrace\ 0,1,2,3\ \rbrace $ は部分集合 $ \lbrace\ 0,1,2,3\ \rbrace $ が要素数が偶数であり、全要素の $ \mathrm{XOR} $ が $ 0 $ であるからです。