No.2683 Two Sheets
タグ : / 解いたユーザー数 74
作問者 :
arad
/ テスター :
👑 
SPD_9X2
👑 
rin204
だれ
kemuniku
kyawa
ma_tw
kosuke-nori
Haowen Li
問題文
縦 $H$ マス、横 $W$ マスからなるグリッドがあり、上から $i$ 行目、左から $j$ 行目にあるマスを $(i,j)$ と呼びます。初めはどのマスも黒く塗られていません。今から高橋君は以下の操作を $2$ 回繰り返します。
- $1$ 以上 $H-A+1$ 以下の整数 $x$ と $1$ 以上 $W-B+1$ 以下の整数 $y$ をそれぞれ独立かつ一様ランダムに選び、左上のマスを $(x,y)$ とする縦 $A$ マス、横 $B$ マスの長方形領域を黒く塗る
高橋君が $2$ 回の操作を終えた後の、黒く塗られたマスの個数の期待値を $\rm{mod}\ 998244353$ で求めてください。
有理数 $\rm{mod}\ 998244353$ の定義
この問題の制約下では求める期待値が必ず有理数になることが証明できます。また、求める期待値を互いに素な正整数 $P$, $Q$ を用いて $P/Q$ のように既約分数で表したとき、 $Q$ が $998244353$ で割り切れないこと、および $P \equiv Q \times R \mod 998244353$ を満たす $0$ 以上 $998244353$ 未満の整数 $R$ が一意に定まることが示せます。この $R$ を求めてください。
入力
$H\ W\ A\ B$
- 入力はすべて整数
- $1\leq A\leq H \leq 2 \times 10^5$
- $1\leq B\leq W \leq 2 \times 10^5$
出力
答えを一行に整数で出力し、最後に改行してください。
サンプル
サンプル1
入力
2 3 1 2
出力
748683268
例えば、1回目の操作で $x=1, y=1$ が選ばれ、2回目の操作で $x=1, y=2$ が選ばれた場合、黒く塗られるマスは $(1,1), (1,2), (1,3)$ の3マスです。
黒く塗られるマスの個数の期待値は $13/4$ となることが示せます。
サンプル2
入力
1 1 1 1
出力
1
サンプル3
入力
13223 2930 50 222
出力
371659179
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。