No.2457 Stampaholic (Easy)
タグ : / 解いたユーザー数 39
作問者 :
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 10^9$
- $1 \leq K \leq \min(H, W, 10^3)$
出力
操作後のグリッド $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
入力
1000 1000 1000000000 1000
出力
1000000
必ず全てのマスが黒色に塗られます。
サンプル3
入力
314159265 358979323 846264338 327
出力
187769831
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。