分数: 400 点
问题陈述
给定整数 N 和 M,计算总和 \displaystyle \sum_{k=0}^{N} \rm{popcount}(k \mathbin{\&} M),模数 998244353.
在这里, \mathbin{\&} 表示按位 \rm{AND} 操作。
什么是按位 \rm{AND} 操作?
结果 x = a \mathbin{\&} b 按位 \rm{AND} 非负整数之间的运算 a 和 b 定义如下:- x 是唯一的非负整数,对于所有非负整数满足以下条件 k:
- 如果 2^k 放置在二进制表示中 a 和 2^k 放置在二进制表示中 b 都是 1,然后 2^k 放置在二进制表示中 x is 1.
- 否则, 2^k 放置在二进制表示中 x is 0.
什么是 \rm{popcount}?
\rm{popcount}(x) 代表数量 1s 的二进制表示形式 x.例如, 13=1101_{(2)},所以 \rm{popcount}(13) = 3.
约束
- N 是介于 0 和 2^{60} - 1,包括在内。
- M 是介于 0 和 2^{60} - 1,包括在内。
输入
输入由标准输入按以下格式给出:
N M
输出
将答案打印为整数。
样本输入 1
4 3
示例输出 1
4
- \rm{popcount}(0\mathbin{\&}3) = 0
- \rm{popcount}(1\mathbin{\&}3) = 1
- \rm{popcount}(2\mathbin{\&}3) = 1
- \rm{popcount}(3\mathbin{\&}3) = 2
- \rm{popcount}(4\mathbin{\&}3) = 0
这些值的总和是 4.
示例输入 2
0 0
示例输出 2
0
有可能 N = 0 or M = 0.
示例输入 3
1152921504606846975 1152921504606846975
示例输出 3
499791890
记住计算结果模数 998244353.