問題一覧 >
通常問題
No.2457 Stampaholic (Easy)
レベル :
/ 実行時間制限 : 1ケース 4.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ :
/
解いたユーザー数 39
作問者 :
srjywrdnprkt
/ テスター :
👑
Nachia
問題文最終更新日: 2023-08-25 20:28:21
この問題は「Stampaholic (Hard)」と同じ設定の問題で,制約のみが異なります。
問題文
全てのマスの色が白である縦 H マス横 W マスのグリッド X に対して、以下の操作をちょうど N 回行います。ここで、マス (i,j) は 上から i 行目、左から j 列目のマスを表し、 K はある与えられた正整数です。
(操作)
1≤i≤H−K+1 かつ 1≤j≤W−K+1 を満たす整数のペア (i,j) を一様ランダムに選び、i≤l≤i+K−1 かつ j≤m≤j+K−1 を満たす全ての整数 (l,m) について、グリッド X のマス (l,m) の色が白ならば、そのマスを黒に塗り替える。
操作後のグリッド X にある黒色のマスの数の期待値は有理数になりますが、その値を mod 998244353 で求めてください。
有理数 mod 998244353 の定義(クリックして詳細を表示)
この問題の制約下では求める期待値を、互いに素な正整数 P, Q を用いて QP のように既約分数で表したとき、Q が 998244353 で割り切れないこと、および P≡Q×R mod 998244353 を満たす 0 以上 998244353 未満の整数 R が一意に定まることが示せます。この R を求めてください。
入力
H W N K
入力は全て整数で以下の制約を満たす。
- 1≤H≤998244352
- 1≤W≤998244352
- 1≤N≤109
- 1≤K≤min(H,W,103)
出力
操作後のグリッド X の黒色のマスの数の期待値を mod 998244353 で出力してください。最後に改行してください。
サンプル
サンプル1
入力
3 3 2 2
出力
249561094
2 回の操作でのマス (i,j) の選び方は全部で 42=16 通りあります。
- 2 回の操作で選んだマスが同じ 4 通りでは、操作後のグリッド X の黒色のマスの数は 4 です。
- 2 回の操作で選んだマスが上下左右で隣接する 8 通りでは、操作後のグリッド X の黒色のマスの数は 6 です。
- それ以外の 4 通りでは、操作後のグリッド X の黒色のマスの数は 7 です。
よって、求める期待値は有理数で表すと 161(4×4+6×8+7×4)=423 となります。
4×249561094 mod 998244353=23 となるので 249561094 が答えです。
サンプル2
入力
1000 1000 1000000000 1000
出力
1000000
必ず全てのマスが黒色に塗られます。
サンプル3
入力
314159265 358979323 846264338 327
出力
187769831
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。