← 返回题目列表

AtCoder · abc356_d

G. 蒙面 Popcount

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

分数: 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.
例如, 3=11_{(2)} 和 5=101_{(2)},所以 3 \mathbin{\&} 5 = 1.
什么是 \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.