No.2457 Stampaholic (Easy)
タグ : / 解いたユーザー数 41
作問者 :
srjywrdnprkt
/ テスター :
👑 
Nachia
Problem Statement
There is a grid $X$ with $H$ rows and $W$ columns in which all cells are white. The following operation is performed on it exactly $N$ times. Here, cell $(i, j)$ denotes the cell in the $i$-th row from the top and the $j$-th column from the left, and $K$ is a given positive integer.
(Operation)
Choose a pair of integers $(i, j)$ satisfying $1 \leq i \leq H-K+1$ and $1 \leq j \leq W-K+1$ uniformly at random. Then, for all integers $(l, m)$ satisfying $i \leq l \leq i+K-1$ and $j \leq m \leq j+K-1$, if the cell $(l, m)$ of grid $X$ is white, repaint that cell black.
The expected number of black cells in grid $X$ after the operations is a rational number. Find this value $\rm{mod}~998244353$.
Definition of a rational number $\rm{mod}~998244353$ (click to show details)
Under the constraints of this problem, it can be shown that when the expected value to be found is written as an irreducible fraction $\frac{P}{Q}$ using coprime positive integers $P,~Q$, $Q$ is not divisible by $998244353$, and an integer $R$ that is at least $0$ and less than $998244353$ satisfying $P \equiv Q\times R~\rm{mod}~998244353$ is uniquely determined. Find this $R$.
Input
$H\ W\ N\ K$
All inputs are integers and satisfy the following constraints.
- $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)$
Output
Output the expected number of black cells in grid $X$ after the operations, $\rm{mod}~ 998244353$. Print a newline at the end.
Sample
Sample 1
Input
3 3 2 2
Output
249561094
There are $4^2 = 16$ ways in total to choose the cells $(i, j)$ over the $2$ operations.
- In the $4$ ways where the cells chosen in the $2$ operations are the same, the number of black cells in grid $X$ after the operations is $4$.
- In the $8$ ways where the cells chosen in the $2$ operations are vertically or horizontally adjacent, the number of black cells in grid $X$ after the operations is $6$.
- In the other $4$ ways, the number of black cells in grid $X$ after the operations is $7$.
Therefore, the expected value to be found, expressed as a rational number, is $\frac{1}{16}(4×4+6×8+7×4)=\frac{23}{4}$.
Since $4×249561094~\rm{mod}~998244353=23$, the answer is $249561094$.
Sample 2
Input
1000 1000 1000000000 1000
Output
1000000
All cells are always painted black.
Sample 3
Input
314159265 358979323 846264338 327
Output
187769831
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。