D - Masked Popcount Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

整数 N,M が与えられるので、 \displaystyle \sum_{k=0}^{N} \rm{popcount}(k \mathbin{\&} M) を 998244353 で割った余りを求めてください。

ただし、 \mathbin{\&} はビット単位 \rm{AND} 演算を表します。

ビット単位 \rm{AND} 演算とは？ 非負整数 a と非負整数 b とのビット単位 \rm{AND} 演算の結果 x = a \mathbin{\&} b は次のように定義されます。
  • x は全ての非負整数 k について以下の条件を満たすただ 1 つの非負整数である。
    • a を 2 進法で書き下した際の 2^k の位と b を 2 進法で書き下した際の 2^k の位が共に 1 なら、 x を 2 進法で書き下した際の 2^k の位は 1 である。
    • そうでないとき、 x を 2 進法で書き下した際の 2^k の位は 0 である。
例えば 3=11_{(2)}, 5=101_{(2)} なので、 3 \mathbin{\&} 5 = 1 となります。
\rm{popcount} とは？ \rm{popcount}(x) は、 x を 2 進法で書き下した際に登場する 1 の個数を表します。
例えば 13=1101_{(2)} なので、 \rm{popcount}(13) = 3 となります。

制約

  • N は 0 以上 2^{60} 未満の整数
  • M は 0 以上 2^{60} 未満の整数

入力

入力は以下の形式で標準入力から与えられる。

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 で割った余りを求めることに注意してください。

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.
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 1s 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.