問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 167
作問者 : Rho / テスター : kaage
10 ProblemId : 4842 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-08-29 23:48:10

問題文

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

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

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

入力

T
N1 K1
...
NT KT

入力は全て整数である
1≤T≤100
1≤N≤109
1≤K≤109

出力

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

サンプル

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

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

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