No.2206 Popcount Sum 2
とりゐ
遭難者問題文最終更新日: 2023-02-03 20:06:00
問題文
$1$ 以上 $2^N$ 未満の整数であって popcount が $M$ 以下になるものすべてについて，その総和を $998244353$ で割った余りを求めてください．
ただし，正整数 $X$ に対して $X$ の popcount とは $X$ を二進数表記したときの $1$ の個数，すなわち $2^k$ の位が $1$ となる非負整数 $k$ の個数のことです．
$1$ つの入力につき $T$ 個のテストケースに答えてください．
入力
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
各テストケースは以下の形式で与えられる．
$N\ M$
- $1\leq T\leq 2\times10^5$
- $1\leq M\leq N\leq 2\times 10^5$
- 入力は全て整数
出力
$T$ 行出力してください．$i$ 行目には $i$ 番目のテストケースの答えを出力してください．
サンプル
サンプル1
入力
3 4 2 10 1 20 10
出力
60 1023 360447725
$1$ つ目のテストケースについて，$1$ 以上 $2^4$ 未満の整数であって popcount が $2$ 以下になるものは $1,2,3,4,5,6,8,9,10,12$ であり，これらの総和は $60$ です．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。