No.2459 Stampaholic (Hard)
タグ : / 解いたユーザー数 21
作問者 :
srjywrdnprkt
/ テスター :
👑 
Nachia
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
Problem Statement
We have a grid $X$ with $H$ rows and $W$ columns, in which all cells are initially 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 every pair of integers $(l, m)$ satisfying $i \leq l \leq i+K-1$ and $j \leq m \leq j+K-1$, if 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 its 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 is expressed as an irreducible fraction $\frac{P}{Q}$ with coprime positive integers $P,~Q$, $Q$ is not divisible by $998244353$, and there is a unique integer $R$ with $0$ or greater and less than $998244353$ satisfying $P \equiv Q\times R~\rm{mod}~998244353$. 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 5 \times 10^5$
- $1 \leq K \leq \min(H, W)$
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 remaining $4$ ways, the number of black cells in grid $X$ after the operations is $7$.
Therefore, the expected value, 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
998244352 998244352 500000 998244352
Output
1
All cells are always painted black. That is, the expected value is $998244352^2 = 996491786299899904$.
Therefore, the answer is $1$, obtained by taking this $\rm{mod}~998244353$.Sample 3
Input
314159265 358979323 84626 43383279
Output
705200769
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。