Masked Popcount

题目描述

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$ .

For example, $3=11_{(2)}$ and $5=101_{(2)}$ , so $3 \mathbin{\&} 5 = 1$ .

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$.

输入格式

The input is given from Standard Input in the following format: $N$ $M$

输出格式

Print the answer as an integer.

4 3

0 0

1152921504606846975 1152921504606846975

499791890

提示

$N$ is an integer between $0$ and $2^{60} - 1$ , inclusive. $M$ is an integer between $0$ and $2^{60} - 1$ , inclusive. $\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$ .
It is possible that $N = 0$ or $M = 0$ .
Remember to compute the result modulo $998244353$ .

标签: AtCoder|abc356D

来源

AtCoder|abc356D

#5108. Masked Popcount

Masked Popcount

Masked Popcount

题目描述

输入格式

输出格式

提示

来源

还没有账户？

登录