問題一覧 > 通常問題

No.2097 AND^k

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 16
作問者 : taiga0629kyoprotaiga0629kyopro / テスター : chineristACchineristAC
5 ProblemId : 8559 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-10-19 17:07:46

問題文

正整数 $N$,$M$,$L$ が与えられます。$k=1,2,\dots,L$ に対して以下の問題を解いてください。

長さが $N$ で各要素が $0$ 以上 $2^M$ 未満の整数である数列 $A$ は $2^{NM}$ 個ありますが、その全てに対する $(A_1\ \mathrm{AND}\ A_2\ \mathrm{AND} \dots \mathrm{AND}\ A_N)^k$ の総和を $998244353$ で割った余りを求めてください。

$\mathrm{AND}$ とは（クリックで開く）

$\mathrm{AND}$ はビットごとの論理積を表します。

入力

$N$ $M$ $L$

  • $1 \le N \le 10^5$
  • $1 \le M \le 10^5$
  • $1 \le L \le 10^5$
  • 入力は全て整数

    • 出力

    $L$ 行出力してください。

    $i$ 行目には、$k=i$ の場合の答えを出力してください。

    サンプル

    サンプル1
    入力
    2 2 2
    出力
    12
24

    $k=1$ のときの求めるべき答えは $\displaystyle \sum_{x=0}^3 \sum_{y=0}^3 (x\ \mathrm{AND}\ y)^1=12$ となります。

    $k=2$ のときの求めるべき答えは $\displaystyle \sum_{x=0}^3 \sum_{y=0}^3 (x\ \mathrm{AND}\ y)^2=24$ となります。

    サンプル2
    入力
    3 3 3
    出力
    448
1568
6496

    サンプル3
    入力
    100 100 5
    出力
    495103078
305228311
29664754
176921287
683149961

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