No.1875 Flip Cards
タグ : / 解いたユーザー数 10
作問者 :
ytqm3
/ テスター :
ぷら
shino16
MtSaka
問題文
かめくんは、 $N$ 種類のカードで遊んでいます。 $i \ (1 \le i \le N)$ 種類目のカードは $C_i$ 枚あり、表には黒で $A_i$ 、裏には赤で $B_i$ と書かれています。
ここで、スコアをカードの表に書いてある数の総積と定義します。
$k=1,2,\ldots,M$ について、次の値を $998244353$ で割った余りを求めてください。
以下の操作を $k$ 回する方法は $(\sum_i C_i)^k$ 通りあるが、そのすべてについての操作終了後の (22:03 追記) スコアの総和
カードを一枚選ぶ。もしカードの表の字の色が黒ならば、裏返して赤字の面を表にする。
ただし、操作において同じ種類のカードもそれぞれ区別して考えるものとします。
入力
$N$ $M$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_N$ $B_N$ $C_N$
- 入力はすべて整数
- $1 \le N,M \le 10^5$
- $1 \le A_i, B_i, C_i \le 998244352$
出力
$M$ 行出力して下さい。 $i$ 行目には、 $k=i$ の時の答えを出力してください。
サンプル
サンプル1
入力
2 2 1 2 1 2 1 1
出力
5 9
$k=2$ の場合を説明します。 $1$ 種類目のカードをカード $1$ 、 $2$ 種類目のカードをカード $2$ と呼ぶことにします。
カード $1$ 、カード $1$ の順で操作をするとスコアは $2\times 2=4$ 、
カード $1$ 、カード $2$ の順で操作をするとスコアは $2\times 1=2$ 、
カード $2$ 、カード $1$ の順で操作をするとスコアは $2\times 1=2$ 、
カード $2$ 、カード $2$ の順で操作をするとスコアは $1\times 1=1$ ですから、スコアの和は $4+2+2+1=9$ です。
サンプル2
入力
2 3 3 1 4 1 5 9
出力
3753 159381 6171489
サンプル3
入力
3 5 265 358 97932384 626 433 83279502 884 197 16939937
出力
405902234 486977455 905998771 23125155 250629615
$998244353$ で割った余りを求めることをお忘れなく。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。