問題一覧 > 通常問題

No.2457 Stampaholic (Easy)

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 39
作問者 : srjywrdnprktsrjywrdnprkt / テスター : 👑 NachiaNachia
0 ProblemId : 9990 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-08-25 20:28:21
この問題は「Stampaholic (Hard)」と同じ設定の問題で,制約のみが異なります。

問題文

全てのマスの色が白である縦 HH マス横 WW マスのグリッド XX に対して、以下の操作をちょうど NN 回行います。ここで、マス (i,j)(i, j) は 上から ii 行目、左から jj 列目のマスを表し、 KK はある与えられた正整数です。

(操作)
1iHK+11 \leq i \leq H-K+1 かつ 1jWK+11 \leq j \leq W-K+1 を満たす整数のペア (i,j)(i, j) を一様ランダムに選び、ili+K1i \leq l \leq i+K-1 かつ jmj+K1j \leq m \leq j+K-1 を満たす全ての整数 (l,m)(l, m) について、グリッド XX のマス (l,m)(l, m) の色が白ならば、そのマスを黒に塗り替える。

操作後のグリッド XX にある黒色のマスの数の期待値は有理数になりますが、その値を mod 998244353\rm{mod}~998244353 で求めてください。

有理数 mod 998244353\rm{mod}~998244353 の定義(クリックして詳細を表示)

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

入力

H W N KH\ W\ N\ K

入力は全て整数で以下の制約を満たす。

  • 1H9982443521 \leq H \leq 998244352
  • 1W9982443521 \leq W \leq 998244352
  • 1N1091 \leq N \leq 10^9
  • 1Kmin(H,W,103)1 \leq K \leq \min(H, W, 10^3)

出力

操作後のグリッド XX の黒色のマスの数の期待値を mod 998244353\rm{mod}~ 998244353 で出力してください。最後に改行してください。

サンプル

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

22 回の操作でのマス (i,j)(i, j) の選び方は全部で 42=164^2 = 16 通りあります。

  • 22 回の操作で選んだマスが同じ 44 通りでは、操作後のグリッド XX の黒色のマスの数は 44 です。
  • 22 回の操作で選んだマスが上下左右で隣接する 88 通りでは、操作後のグリッド XX の黒色のマスの数は 66 です。
  • それ以外の 44 通りでは、操作後のグリッド XX の黒色のマスの数は 77 です。

よって、求める期待値は有理数で表すと 116(4×4+6×8+7×4)=234\frac{1}{16}(4×4+6×8+7×4)=\frac{23}{4} となります。

4×249561094 mod 998244353=234×249561094~\rm{mod}~998244353=23 となるので 249561094249561094 が答えです。

サンプル2
入力
1000 1000 1000000000 1000
出力
1000000

必ず全てのマスが黒色に塗られます。

サンプル3
入力
314159265 358979323 846264338 327
出力
187769831

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