#P13664. [ARC146C] Even XOR

    ID: 12866 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-奇偶性分析双射计数乘法原理重复元素除重递推计数逆元线性递推GF(2) 线性无关计数

[ARC146C] Even XOR

题目描述

请求出由 [0,2N)[0,2^N) 的非负整数组成的集合 SS 中,满足以下条件的集合的个数对 998244353998244353 取模的结果。

  • SS 的任意非空子集 TT 都满足以下两者之一:
    • TT 的元素个数为奇数;
    • TT 所有元素的 XOR\mathrm{XOR} 不为 00。

::::info[什么是 XOR\mathrm{XOR}?]

XOR\mathrm{XOR} 指的是非负整数 A,BA, B 的按位异或,记作 A⊕BA \oplus B,定义如下:

  • A⊕BA \oplus B 的二进制表示中,第 2k2^k 位(k≥0k \geq 0)的数,如果 A,BA, B 的二进制表示中该位只有一个为 11,则该位为 11,否则为 00。

例如,3⊕5=63 \oplus 5 = 6(二进制为:011⊕101=110011 \oplus 101 = 110)。 一般地,kk 个整数 p1,p2,p3,…,pkp_1, p_2, p_3, \dots, p_k 的按位 XOR\mathrm{XOR} 定义为 $((\dots((p_1 \oplus p_2) \oplus p_3) \oplus \dots) \oplus p_k)$,并且可以证明,这个值与 p1,p2,…,pkp_1, p_2, \dots, p_k 的顺序无关。

输入格式

输入为以下格式,从标准输入读取。

NN

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2

输出 #1

15

输入输出样例 #2

输入 #2

146

输出 #2

743874490

说明/提示

限制

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 输入均为整数。

样例解释 1

{0,2,3}\lbrace 0,2,3 \rbrace、{1}\lbrace 1 \rbrace、{}\lbrace \rbrace 等集合满足条件。{0,1,2,3}\lbrace 0,1,2,3 \rbrace 不满足条件,因为它的子集 {0,1,2,3}\lbrace 0,1,2,3 \rbrace 的元素个数为偶数,且所有元素的 XOR\mathrm{XOR} 为 00。