H. 【普及】二进制中1的个数

A B C D E F G H I

传统题

100ms

32MiB

【普及】二进制中1的个数

给定整数 $n$ 和 $m$ ，计算和

$$\displaystyle \sum_{k=0}^{n} \rm{popcount} (k \mathbin{\&} m) \bmod 998244353$$

这里， $\mathbin{\&}$ 表示位操作 $\rm{AND}$ 。

什么是 & 运算？

$0 \mathbin{\&} 0 = 0$
$0 \mathbin{\&} 1 = 0$
$1 \mathbin{\&} 0 = 0$
$1 \mathbin{\&} 1 = 1$
也就是只有 $2$ 个 1 结果才是 $1$ ，否则结果为 $0$

什么是 popcount

$\rm{popcount}$ $(x)$ 表示 $x$ 的二进制表示中 $1$ 的个数，比如：

$13=1101_{(2)}$ ，所以是 $\rm{popcount}$ $(13) = 3$ 。

输入格式

输入一行包含 $2$ 个正整数 $n, m(0 \le n, m \le 2^{60} - 1)$

请注意 $n, m$ 的数据范围！！

输出格式

对于每组数据输出一行，包含答案

4 3

1152921504606846975 1152921504606846975

499791890

提示

【样例 1 解释】

$\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$
答案为： $0+1+1+2+0=4$
请注意将最后的答案对 998244353 取模

【数据范围】

$0 \le n, m \le 2^{60} - 1$

请思考后再点击查看提示

来源

参考答案

【算法入门-16】贡献思维和单调栈

状态: 正在进行…
题目: 9
开始时间: 2025-11-8 8:00
截止时间: 2027-8-16 23:59
可延期: 24 小时