← 返回题目列表

AtCoder · tupc2024_c

C. 2 的幂冲刺

中文机器翻译题面 查看原题

配点 : {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 。
例如, 3 \oplus 5 = 6 (二进制表示法: 011 \oplus 101=110)。

制約

  • 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 。