問題一覧 > 通常問題

No.1206 OR, OR, OR......

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 116
作問者 : RhoRho / テスター : kaagekaage
4 ProblemId : 4842 / 出題時の順位表
問題文最終更新日: 2020-08-29 23:48:10

問題文

集合 $I$ を、 $0$ 以上 $N-1$ 以下の整数を1つずつ含む集合と定義します。
また、$I$ の部分集合 $J_1 , J_2 , ... J_K $ をそれぞれ任意にとります。

このとき、 $K$ 個の部分集合 $J_1 , J_2 , ... J_K $ の組に対する美しさを, これらの和集合の要素数と定義します。(和集合の正確な定義はこちら)
全ての $J_1, J_2, ... J_K$ の選び方に対して美しさの総和を計算してください。
答えは非常に大きくなることがあるので、 $998 244 353$ で割った余りを求めてください。

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

入力

$T$
$N_1\ K_1$
...
$N_T\ K_T$

入力は全て整数である
$1 \leq T \leq 100$
$1 \leq N \leq 10^9$
$1 \leq K \leq 10^9$

出力

$T$ 行にわたって出力してください。$i$ 行目には、$i$ 番目の答を $998 244 353$ で割った余りを一行に出力してください。
最後に改行してください。

サンプル

サンプル1
入力
3
1 2
3 7
172894913 183245832
出力
3
6242304
358532619

以下は2行目のテストケースに関する説明です。
集合 $I=\{0\}$ です。また、 $(J_1, J_2)$ の組として考えられるものは $(\{\},\{\}), (\{\},\{0\}), (\{0\},\{\}), (\{0\},\{0\})$ の4通りです。
それぞれの美しさは左から順に $0, 1, 1, 1$ で、その総和である $3$ を出力します。

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