No.2206 Popcount Sum 2
Problem Statement
Find the sum of all integers that are at least $1$ and less than $2^N$ and whose popcount is at most $M$, modulo $998244353$.
Here, for a positive integer $X$, the popcount of $X$ is the number of $1$s in the binary representation of $X$, that is, the number of non-negative integers $k$ such that the $2^k$ digit is $1$.
Answer $T$ test cases for $1$ input.
Input
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
Each test case is given in the following format.
$N\ M$
- $1\leq T\leq 2\times10^5$
- $1\leq M\leq N\leq 2\times 10^5$
- All inputs are integers.
Output
Print $T$ lines. The $i$-th line should contain the answer to the $i$-th test case.
Sample
Sample 1
Input
3 4 2 10 1 20 10
Output
60 1023 360447725
For test case number $1$, the integers that are at least $1$ and less than $2^4$ and whose popcount is at most $2$ are $1,2,3,4,5,6,8,9,10,12$, and their sum is $60$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
とりゐ