問題一覧 > 通常問題

No.2499 Sum of Products of Sums

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 27
作問者 : KumaTachiRenKumaTachiRen / テスター : とりゐとりゐ
6 ProblemId : 9562 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-09-11 11:53:09

問題文

$H$ 行 $W$ 列のマス目があります．このマス目の各マスに，次の条件をみたすように非負整数を $1$ つずつ書き込むことを考えます．

  • $i=1,2,\dots,H$ について，$i$ 行目に書かれた数の総和は $A_i$ 以上 $B_i$ 以下である．
$j$ 列目に書かれた数の総和を $S_j$ としたとき，その書き込み方のスコアを $S_1,S_2,\dots,S_W$ の総積 $S_1S_2\cdots S_W$ として定めます． 書き込み方としてありうるもの全てに対するスコアの総和を $998244353$ で割ったあまりを求めてください．

入力

$H\ W$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_H\ B_H$

  • $1\leq H\leq 1000$
  • $1\leq W\leq 1000$
  • $0\leq A_i\leq B_i\leq 10^9$
  • 入力は全て整数

出力

答えを出力してください． 最後に改行してください．

サンプル

サンプル1
入力
2 2
1 1
1 2
出力
10

あり得る書き込み方は次の $10$ 通りです． \[ \begin{array}{|c|c|}\hline 0&1\\\hline 0&1\\\hline\end{array},\ \begin{array}{|c|c|}\hline 0&1\\\hline 0&2\\\hline\end{array},\ \begin{array}{|c|c|}\hline 0&1\\\hline 1&0\\\hline\end{array},\ \begin{array}{|c|c|}\hline 0&1\\\hline 1&1\\\hline\end{array},\ \begin{array}{|c|c|}\hline 0&1\\\hline 2&0\\\hline\end{array},\ \begin{array}{|c|c|}\hline 1&0\\\hline 0&1\\\hline\end{array},\ \begin{array}{|c|c|}\hline 1&0\\\hline 0&2\\\hline\end{array},\ \begin{array}{|c|c|}\hline 1&0\\\hline 1&0\\\hline\end{array},\ \begin{array}{|c|c|}\hline 1&0\\\hline 1&1\\\hline\end{array},\ \begin{array}{|c|c|}\hline 1&0\\\hline 2&0\\\hline\end{array} \] それぞれのスコアは $0,0,1,2,2,1,2,0,2,0$ であり，総和は $10$ です．

サンプル2
入力
3 14
183 294
642 753
507 618
出力
725318175

$998244353$ で割ったあまりを出力してください．

サンプル3
入力
10 1000
119739043 300863646
375955574 841722934
182790546 316482342
261031712 376334636
444712348 563110304
233166140 806084221
603172199 911295633
783239093 877375821
396848627 629360609
663094820 814992500
出力
287672754

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