No.2983 Christmas Color Grid (Advent Calender ver.)
タグ : / 解いたユーザー数 19
作問者 :
hirayuu_yc
/ テスター :
highlighter
👑 
p-adic
Note
Note that the time limit and memory limit of this problem are $3340~\text{ms},~128~\text{MB}$, respectively. Also, the execution time of the writer's solution implemented in PyPy3 is $2546~\text{ms}$.
Problem Statement
There is an advent calendar with $H$ rows and $W$ columns of cells. The cell in the $i$-th row from the top and the $j$-th from the left of this advent calendar is denoted by cell $(i,j)$. Initially, no cell is colored.
At first, Haruku's happiness is $0$. Haruku performs the following sequence of operations $HW$ times.
- Choose at random a cell of the advent calendar that has not been colored yet. With probability $\dfrac{1}{2}$ paint that cell green, and with probability $\dfrac{1}{2}$ paint that cell red.
- Let $X$ be the expected value of the sum of the $K$-th powers of the sizes of the green connected components when the remaining operations have been completed, and let $Y$ be the number of cells of the advent calendar that have not been colored yet. Add $\dfrac{X}{Y+1}$ to Haruku's happiness.
Here, consider the undirected graph on the advent calendar whose vertex set is the set of cells painted green and whose edge set consists of all edges connecting $2$ adjacent green cells. The sum of the $K$-th powers of the sizes of the connected components of this graph is called the sum of the $K$-th powers of the sizes of the green connected components. Two cells $(x,y)$ and $(x^′,y^′)$, that is, $2$ cells, are said to be adjacent if and only if $|x−x^′|+|y−y^′|=1$.
Output the expected value of Haruku's final happiness $\bmod~M$.
What "output the expected value $\bmod~M$" means
It can be proved that the value to be found is always a rational number. Moreover, under the constraints of this problem, it can be proved that when the value is expressed as $\dfrac{P}{Q}$ using coprime integers $P,Q$, there is exactly $1$ integer $R$ such that $R\times Q\equiv P~(\bmod~M)$ and $0\leq R\lt M$. Output this $R$.Constraints
- $1\leq H,W$
- $HW\leq 25$
- $0\leq K\leq 10^{18}$
- $10^8\leq M\leq 10^9+7$
- $M$ is prime.
- All input values are integers.
Input
The input is given from standard input in the following format.
$H$ $W$ $K$ $M$
Output
Output the answer.
Sample
Sample 1
Input
1 1 0 998244353
Output
499122177
When $K=0$, the sum of the $K$-th powers of the sizes of the green connected components equals the number of green connected components.
Haruku gets a happiness of $0$ with probability $\dfrac{1}{2}$ and a happiness of $1$ with probability $\dfrac{1}{2}$. Therefore, the expected value is $\dfrac{1}{2}$.
Since $499122177\times 2\equiv 1~(\bmod~998244353)$, the answer is $499122177$.
Sample 2
Input
3 1 1 998244353
Output
249561091
When $K=1$, the sum of the $K$-th powers of the sizes of the green connected components equals the number of green cells.
Sample 3
Input
5 5 1000000000000000000 1000000007
Output
530357272
When it comes to advent calendars, $5\times 5$ is the size.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。