問題一覧 > 通常問題

No.1875 Flip Cards

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 11
作問者 : ytqm3ytqm3 / テスター : ぷらぷら shino16shino16 MtSakaMtSaka
1 ProblemId : 7287 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-11-12 15:38:43

問題文

かめくんは、 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。