No.2459 Stampaholic (Hard)
タグ : / 解いたユーザー数 20
作問者 :
srjywrdnprkt
/ テスター :
👑 
Nachia
問題文
全てのマスの色が白である縦 $H$ マス横 $W$ マスのグリッド $X$ に対して、以下の操作をちょうど $N$ 回行います。ここで、マス $(i, j)$ は 上から $i$ 行目、左から $j$ 列目のマスを表し、 $K$ はある与えられた正整数です。
(操作)
$1 \leq i \leq H-K+1$ かつ $1 \leq j \leq W-K+1$ を満たす整数のペア $(i, j)$ を一様ランダムに選び、$i \leq l \leq i+K-1$ かつ $j \leq m \leq j+K-1$ を満たす全ての整数 $(l, m)$ について、グリッド $X$ のマス $(l, m)$ の色が白ならば、そのマスを黒に塗り替える。
操作後のグリッド $X$ にある黒色のマスの数の期待値は有理数になりますが、その値を $\rm{mod}~998244353$ で求めてください。
有理数 $\rm{mod}~998244353$ の定義(クリックして詳細を表示)
この問題の制約下では求める期待値を、互いに素な正整数 $P,~Q$ を用いて $\frac{P}{Q}$ のように既約分数で表したとき、$Q$ が $998244353$ で割り切れないこと、および $P \equiv Q\times R~\rm{mod}~998244353$ を満たす $0$ 以上 $998244353$ 未満の整数 $R$ が一意に定まることが示せます。この $R$ を求めてください。
入力
$H\ W\ N\ K$
入力は全て整数で以下の制約を満たす。
- $1 \leq H \leq 998244352$
- $1 \leq W \leq 998244352$
- $1 \leq N \leq 5 \times 10^5$
- $1 \leq K \leq \min(H, W)$
出力
操作後のグリッド $X$ の黒色のマスの数の期待値を $\rm{mod}~ 998244353$ で出力してください。最後に改行してください。
サンプル
サンプル1
入力
3 3 2 2
出力
249561094
$2$ 回の操作でのマス $(i, j)$ の選び方は全部で $4^2 = 16$ 通りあります。
- $2$ 回の操作で選んだマスが同じ $4$ 通りでは、操作後のグリッド $X$ の黒色のマスの数は $4$ です。
- $2$ 回の操作で選んだマスが上下左右で隣接する $8$ 通りでは、操作後のグリッド $X$ の黒色のマスの数は $6$ です。
- それ以外の $4$ 通りでは、操作後のグリッド $X$ の黒色のマスの数は $7$ です。
よって、求める期待値は有理数で表すと $\frac{1}{16}(4×4+6×8+7×4)=\frac{23}{4}$ となります。
$4×249561094~\rm{mod}~998244353=23$ となるので $249561094$ が答えです。
サンプル2
入力
998244352 998244352 500000 998244352
出力
1
必ず全てのマスが黒色に塗られます。つまり、期待値は $998244352^2 = 996491786299899904$ となります。
よって、$\rm{mod}~998244353$ をとった $1$ が答えになります。サンプル3
入力
314159265 358979323 84626 43383279
出力
705200769
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。