問題一覧 > 通常問題

No.2499 Sum of Products of Sums

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

問題文

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

  • i=1,2,…,Hi=1,2,\dots,H について，ii 行目に書かれた数の総和は AiA_i 以上 BiB_i 以下である．
jj 列目に書かれた数の総和を SjS_j としたとき，その書き込み方のスコアを S1,S2,…,SWS_1,S_2,\dots,S_W の総積 S1S2⋯SWS_1S_2\cdots S_W として定めます． 書き込み方としてありうるもの全てに対するスコアの総和を 998244353998244353 で割ったあまりを求めてください．

入力

H WH\ W
A1 B1A_1\ B_1
A2 B2A_2\ B_2
⋮\vdots
AH BHA_H\ B_H

  • 1≤H≤10001\leq H\leq 1000
  • 1≤W≤10001\leq W\leq 1000
  • 0≤Ai≤Bi≤1090\leq A_i\leq B_i\leq 10^9
  • 入力は全て整数

出力

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

サンプル

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

あり得る書き込み方は次の 1010 通りです． 0101, 0102, 0110, 0111, 0120, 1001, 1002, 1010, 1011, 1020 \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,00,0,1,2,2,1,2,0,2,0 であり，総和は 1010 です．

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

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

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