問題一覧 > 通常問題

No.2206 Popcount Sum 2

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 52
作問者 : とりゐとりゐ / テスター : 遭難者遭難者
6 ProblemId : 9056 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-02-03 20:06:00

問題文

11 以上 2N2^N 未満の整数であって popcount が MM 以下になるものすべてについて,その総和を 998244353998244353 で割った余りを求めてください.
ただし,正整数 XX に対して XX の popcount とは XX を二進数表記したときの 11 の個数,すなわち 2k2^k の位が 11 となる非負整数 kk の個数のことです.
11 つの入力につき TT 個のテストケースに答えてください.

入力

TT
case1\mathrm{case}_1
case2\mathrm{case}_2
\vdots
caseT\mathrm{case}_T
各テストケースは以下の形式で与えられる.
N MN\ M

  • 1T2×1051\leq T\leq 2\times10^5
  • 1MN2×1051\leq M\leq N\leq 2\times 10^5
  • 入力は全て整数

出力

TT 行出力してください.ii 行目には ii 番目のテストケースの答えを出力してください.

サンプル

サンプル1
入力
3
4 2
10 1
20 10
出力
60
1023
360447725

11 つ目のテストケースについて,11 以上 242^4 未満の整数であって popcount が 22 以下になるものは 1,2,3,4,5,6,8,9,10,121,2,3,4,5,6,8,9,10,12 であり,これらの総和は 6060 です.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。