103563: [Atcoder]ABC356 D - Masked Popcount
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：8
Solved：0
Description
Score : $400$ points
Problem Statement
Given integers $N$ and $M$, compute the sum $\displaystyle \sum_{k=0}^{N}$ $\rm{popcount}$$(k \mathbin{\&} M)$, modulo $998244353$.
Here, $\mathbin{\&}$ represents the bitwise $\rm{AND}$ operation.
What is the bitwise $\rm{AND}$ operation?
The result $x = a \mathbin{\&} b$ of the bitwise $\rm{AND}$ operation between non-negative integers $a$ and $b$ is defined as follows:- $x$ is the unique non-negative integer that satisfies the following conditions for all non-negative integers $k$:
- If the $2^k$ place in the binary representation of $a$ and the $2^k$ place in the binary representation of $b$ are both $1$, then the $2^k$ place in the binary representation of $x$ is $1$.
- Otherwise, the $2^k$ place in the binary representation of $x$ is $0$.
What is $\rm{popcount}$?
$\rm{popcount}$$(x)$ represents the number of $1$s in the binary representation of $x$.For example, $13=1101_{(2)}$, so $\rm{popcount}$$(13) = 3$.
Constraints
- $N$ is an integer between $0$ and $2^{60} - 1$, inclusive.
- $M$ is an integer between $0$ and $2^{60} - 1$, inclusive.
Input
The input is given from Standard Input in the following format:
$N$ $M$
Output
Print the answer as an integer.
Sample Input 1
4 3
Sample Output 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$
The sum of these values is $4$.
Sample Input 2
0 0
Sample Output 2
0
It is possible that $N = 0$ or $M = 0$.
Sample Input 3
1152921504606846975 1152921504606846975
Sample Output 3
499791890
Remember to compute the result modulo $998244353$.
Output
得分：400分
例如，$13=1101_{(2)}$，所以 $\rm{popcount}$$(13) = 3$。
问题描述
给定整数 $N$ 和 $M$，计算和 $\displaystyle \sum_{k=0}^{N}$ $\rm{popcount}$$(k \mathbin{\&} M)$，对 $998244353$ 取模。
其中，$\mathbin{\&}$ 代表位与操作。
位与操作是什么？
位与操作是非负整数 $a$ 和 $b$ 之间的运算，其结果 $x = a \mathbin{\&} b$ 定义如下：- $x$ 是唯一满足以下条件的非负整数，对于所有非负整数 $k$：
- 如果 $a$ 的二进制表示中第 $2^k$ 位和 $b$ 的二进制表示中第 $2^k$ 位都是 $1$，那么 $x$ 的二进制表示中第 $2^k$ 位是 $1$。
- 否则，$x$ 的二进制表示中第 $2^k$ 位是 $0$。
什么是 $\rm{popcount}$？
$\rm{popcount}$$(x)$ 表示整数 $x$ 的二进制表示中 $1$ 的个数。例如，$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$ 或 $M = 0$ 的情况。
样例输入 3
1152921504606846975 1152921504606846975
样例输出 3
499791890
记得对结果取模 $998244353$。