2-Power Rush
如果一个正整数多重集的每个元素都是 2 的非负整数次幂,就称它为好集合。多重集允许相同元素重复出现,元素的排列顺序不区分集合。
对非负整数 N,记 SN 为所有元素之和等于 N 的好集合构成的集合。定义
f(N)=X∈SN∑ x∈X∏x.
约定空多重集的元素和为 0,元素乘积为 1,因此 f(0)=1。
给定整数 T,a,b。对 i=0,1,…,T−1,定义
Ni=(ai+b)mod230.
请计算
$$\sum_{i=0}^{T-1}\left(\bigl(f(N_i)\bmod998244353\bigr)\mathbin{\oplus}i\right),$$
其中 ⊕ 表示按位异或。每一项先对 f(Ni) 取模,再与 i 异或;最终总和不再取模。
输入格式
一行三个整数 T,a,b。
输出格式
输出一行一个整数,表示要求的总和。
数据范围
- 1≤T≤107;
- 0≤a,b<230;
- 所有输入值均为整数。
样例 1
样例输入 1
5 1 0
样例输出 1
17
样例 2
样例输入 2
3 1000000000 1000000000
样例输出 2
1217611736
样例说明
第一个样例中,N0,…,N4 依次为 0,1,2,3,4。
- 和为 0 的好集合只有空集,因此 f(0)=1。
- 和为 1 的好集合只有 {1},因此 f(1)=1。
- 和为 2 的好集合为 {1,1},{2},因此 f(2)=1+2=3。
- 和为 3 的好集合为 {1,1,1},{1,2},因此 f(3)=1+2=3。
- 和为 4 的好集合为 {1,1,1,1},{1,1,2},{2,2},{4},因此 f(4)=1+2+4+4=11。
答案为 $(1\oplus0)+(1\oplus1)+(3\oplus2)+(3\oplus3)+(11\oplus4)=17$。
第二个样例中,N0,N1,N2 分别为 1000000000,926258176,852516352。