配点 : {100} 点
問題文
正整数的多重集合是 好的集合 的定义是,所包含的元素全部 2 是幂。 对
非負整数 N 来说,元素的总和为 N 这样的每一个良好集合,当计算其元素的总乘积时,将这些总和记为 f(N) 。其中,空集合的元素总和为 0,总乘积为 1 作为 f(0)=1 。
非負整数 T,a,b 。 对于 N_i=(ai+b)\ \mathrm{mod}\ 2^{30} 当 \displaystyle \sum_{i=0}^{T-1}(f(N_i)\ \mathrm{mod}\ 998244353)\oplus i 。这里, \oplus 是按位异或。
什么是按位异或?
非負整数 A,B 的按位异或 (XOR) A \oplus B 定义如下。 当- A \oplus B 以二进制表示法 2^k \, (k \geq 0) 中的位数为A,B 以二进制表示法 2^k 数字中只有一位是 1 如果 1,否则 输出为 0 。
制約
- 1\leq T\leq 10^7
- 0\leq a,b\lt 2^{30}
- 所有输入均为整数
部分点
这个问题有多个部分点。 如果正确答案是满足
- 附加限制 如果正确答案是满足 T\leq 10^6,a=1,b=0 的数据集 给出 10 点。 如果您正确回答了所有满足
- 附加限制 如果正确答案是满足 T\leq 1000 的数据集 给出 10 点。 如果您正确回答了所有满足
入力
输入是按以下格式从标准输入给出的。
T a b
出力
打印答案。 来自
入力例 1
5 1 0
出力例 1
17
N_0=0,N_1=1,N_2=2,N_3=3,N_4=4 。
- 总和是 正整数序列,使得 0 是好的集合 \lbrace\rbrace 和 f(0)=1 。
- 总和是 正整数序列,使得 1 是好的集合 \lbrace1\rbrace 和 f(1)=1 。
- 总和是 正整数序列,使得 2 是好的集合 \lbrace1,1\rbrace,\lbrace2\rbrace 和 f(2)=(1\times 1)+(2)=3 。
- 总和是 正整数序列,使得 3 是好的集合 \lbrace1,1,1\rbrace,\lbrace1,2\rbrace 和 f(3)=(1\times 1\times 1)+(1\times 2)=3 。
- 总和是 正整数序列,使得 4 是好的集合 \lbrace1,1,1,1\rbrace,\lbrace1,1,2\rbrace,\lbrace2,2\rbrace,\lbrace4\rbrace 和 f(4)=(1\times 1\times 1\times 1)+(1\times 1\times 2)+(2\times 2)+(4)=11 。
因此,您正在寻找的答案是 (1\oplus 0)+(1\oplus 1)+(3\oplus 2)+(3\oplus 3)+(11\oplus 4)=17 。
入力例 2
3 1000000000 1000000000
出力例 2
1217611736
N_0=1000000000,N_1=926258176,N_2=852516352 。