E - Popcount Sum 3 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

正の整数 N,K が与えられます。
N 以下の正の整数 x であって、次の条件をみたすものの 総和 を 998244353 で割った余りを求めてください。

  • x の popcount の値はちょうど K である。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

popcount とは 正整数 y に対して、y の popcount の値 \mathrm{popcount}(y) は、y を二進数表記したとき 1 となっている桁の個数を表します。 例えば、\mathrm{popcount}(5)=2, \mathrm{popcount}(16)=1, \mathrm{popcount}(25)=3 です。

制約

  • 1\leq T\leq 100
  • 1\leq N < 2^{60}
  • 1\leq K \leq 60
  • T,N,K は整数

入力

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

\mathrm{case}_i は i 番目のテストケースを表す。 各テストケースは以下の形式で与えられる。

N K

出力

T 行出力せよ。i 行目 (1\leq i\leq T) には i 番目のテストケースに対する答えを出力せよ。

入力例 1

2
20 2
1234567890 17

出力例 1

100
382730918

1 番目のテストケースについて、20 以下の正の整数のうち、popcount の値が 2 であるものは 3,5,6,9,10,12,17,18,20 の 9 つであり、その総和は 100 となります。
100 を 998244353 で割った余りは 100 であるため、1 行目には 100 を出力します。
998244353 で割った余りを出力する必要があることに注意してください。

Score : 450 points

Problem Statement

You are given positive integers N and K.
Find the sum, modulo 998244353, of all positive integers x that do not exceed N and satisfy the following condition:

  • the popcount of x is exactly K.

You are given T test cases; solve each of them.

What is popcount? For a positive integer y, \mathrm{popcount}(y) denotes the number of 1 bits in the binary representation of y. For example, \mathrm{popcount}(5)=2, \mathrm{popcount}(16)=1, \mathrm{popcount}(25)=3.

Constraints

  • 1 \leq T \leq 100
  • 1 \leq N < 2^{60}
  • 1 \leq K \leq 60
  • T, N, and K are integers.

Input

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

\mathrm{case}_i denotes the i-th test case. Each test case is given in the following format:

N K

Output

Output T lines. The i-th line (1 \leq i \leq T) should contain the answer for the i-th test case.

Sample Input 1

2
20 2
1234567890 17

Sample Output 1

100
382730918

For the first test case, there are nine positive integers not exceeding 20 whose popcount is 2: 3, 5, 6, 9, 10, 12, 17, 18, 20. Their sum is 100.
The remainder when 100 is divided by 998244353 is 100, so output 100 on the first line.
Remember to output the sum modulo 998244353.