C - Powers of Subsets' sum
問題文
正整数 $N,K$ と長さ $N$ の正整数列 $A = (A_1, A_2, \ldots, A_N)$ が与えられます。
集合 $S$ を、$1$ 以上 $N$ 以下のすべての整数を要素とする集合と定義します。
また、$S$ の空でない部分集合 $T$ について、$f(T) = \left( \sum\limits_{i \in T} A_{i} \right)^K$ と定めます。
$T$ としてありうる部分集合は $2^N - 1$ 個ありますが、それらすべてに対する $f(T)$ の総和を $998244353$ で割った余りを求めてください。
制約
- $1 \leq N \leq 10^{5}$
- $1 \leq K \leq 10^{5}$
- $1 \leq A_{i} \lt 998244353$
- 入力はすべて整数である
部分点
set1$(10$ 点$)$：$N \leq 2000$ かつ $K = 1$set2$(20$ 点$)$：$N \leq 2000$ かつ $K \leq 2000$all$(70$ 点$)$：追加の制約はない
入力
入力は以下の形式で標準入力から与えられます。
$N$ $K$
$A_1$ $A_2$ $\ldots$ $A_N$
出力
答えを出力してください。
3 1
1 2 3
24
$f(\lbrace 1 \rbrace) + f(\lbrace 2 \rbrace) + f(\lbrace 3 \rbrace) + f(\lbrace 1, 2 \rbrace) + f(\lbrace 1, 3 \rbrace) + f(\lbrace 2, 3 \rbrace) + f(\lbrace 1, 2, 3 \rbrace) = 1^1 + 2^1 + 3^1 + 3^1 + 4^1 + 5^1 + 6^1 = 24$ です。
この入力例は部分点 set1, set2 の制約を満たします。
3 2
1 2 3
100
$f(\lbrace 1 \rbrace) + f(\lbrace 2 \rbrace) + f(\lbrace 3 \rbrace) + f(\lbrace 1, 2 \rbrace) + f(\lbrace 1, 3 \rbrace) + f(\lbrace 2, 3 \rbrace) + f(\lbrace 1, 2, 3 \rbrace) = 1^2 + 2^2 + 3^2 + 3^2 + 4^2 + 5^2 + 6^2 = 1 + 4 + 9 + 9 + 16 + 25 + 36 = 100$ です。
この入力例は部分点 set2 の制約を満たします。
5 100
1 2 3 4 5
13037257
この入力例は部分点 set2 の制約を満たします。
6 100000
22978189 416566305 229015844 810969914 581133972 66830749
414421061