問題一覧 > 通常問題

No.2683 Two Sheets

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 78
作問者 : arad / テスター : 👑 tute7627 👑 SPD_9X2 👑 rin204 だれ kemuniku kyawa ma_tw kosuke-nori Haowen Li
4 ProblemId : 10422 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-20 18:27:57

問題文

縦 HH マス、横 WW マスからなるグリッドがあり、上から ii 行目、左から jj 行目にあるマスを (i,j)(i,j) と呼びます。初めはどのマスも黒く塗られていません。今から高橋君は以下の操作を 22 回繰り返します。

  • 11 以上 H−A+1H-A+1 以下の整数 xx と 11 以上 W−B+1W-B+1 以下の整数 yy をそれぞれ独立かつ一様ランダムに選び、左上のマスを (x,y)(x,y) とする縦 AA マス、横 BB マスの長方形領域を黒く塗る

高橋君が 22 回の操作を終えた後の、黒く塗られたマスの個数の期待値を mod 998244353\rm{mod}\ 998244353 で求めてください。

有理数 mod 998244353\rm{mod}\ 998244353 の定義

この問題の制約下では求める期待値が必ず有理数になることが証明できます。また、求める期待値を互いに素な正整数 PP, QQ を用いて P/QP/Q のように既約分数で表したとき、 QQ が 998244353998244353 で割り切れないこと、および P≡Q×Rmod  998244353P \equiv Q \times R \mod 998244353 を満たす 00 以上 998244353998244353 未満の整数 RR が一意に定まることが示せます。この RR を求めてください。

入力

H W A BH\ W\ A\ B

  • 入力はすべて整数
  • 1≤A≤H≤2×1051\leq A\leq H \leq 2 \times 10^5
  • 1≤B≤W≤2×1051\leq B\leq W \leq 2 \times 10^5

出力

答えを一行に整数で出力し、最後に改行してください。

サンプル

サンプル1
入力
2 3 1 2
出力
748683268

例えば、1回目の操作で x=1,y=1x=1, y=1 が選ばれ、2回目の操作で x=1,y=2x=1, y=2 が選ばれた場合、黒く塗られるマスは (1,1),(1,2),(1,3)(1,1), (1,2), (1,3) の3マスです。

黒く塗られるマスの個数の期待値は 13/413/4 となることが示せます。

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

サンプル3
入力
13223 2930 50 222
出力
371659179

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