No.2983 Christmas Color Grid (Advent Calender ver.)
タグ : / 解いたユーザー数 18
作問者 :
hirayuu_yc
/ テスター :
highlighter
👑 
p-adic
注意
この問題の実行時間制限、メモリ制限はそれぞれ $3340~\text{ms},~128~\text{MB}$ であることに注意してください。また、Writer解のPyPy3での実装の実行時間は $2546~\text{ms}$ です。
問題文
縦 $H$ マス、横 $W$ マスのアドベントカレンダーがあります。このアドベントカレンダーの上から $i$ 行目、左から $j$ 行目のマスをマス $(i,j)$ と表記します。初期状態ではどのマスにも色は塗られていません。
はじめ、はるく君のうれしさは $0$ です。はるく君は、以下の一連の操作を $HW$ 回行います。
- アドベントカレンダーのまだ色が塗られていないマスを無作為に選ぶ。確率 $\dfrac{1}{2}$ でそのマスを緑に塗り、確率 $\dfrac{1}{2}$ でそのマスを赤に塗る。
- この後の操作を完遂したときの緑の連結成分の大きさの $K$ 乗和の期待値を$X$ とし、アドベントカレンダーのまだ色が塗られていないマスの数を $Y$ とする。$\dfrac{X}{Y+1}$ をはるく君のうれしさに加算する。
ここで、アドベントカレンダーにおいて、緑色に塗られたマスを頂点集合、隣り合った $2$ つの緑色のマスを結ぶ辺全体を辺集合とした無向グラフにおける連結成分の大きさの $K$ 乗和を緑の連結成分の大きさの $K$ 乗和と呼びます。ただし、$2$ つのマス $(x,y)$ と $(x^′,y^′)$ が隣り合っているとは、$|x−x^′|+|y−y^′|=1$ であることを指します。
最終的なはるく君のうれしさの期待値を $\bmod~M$ で出力してください。
「期待値を $\bmod~M$ で出力」とは
求める値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な整数 $P,Q$ を用いて $\dfrac{P}{Q}$ と表したとき、$R\times Q\equiv P~(\bmod~M)$ かつ $0\leq R\lt M$ なる整数 $R$ がただ $1$ つ存在することが証明できます。この $R$ を出力してください。制約
- $1\leq H,W$
- $HW\leq 25$
- $0\leq K\leq 10^{18}$
- $10^8\leq M\leq 10^9+7$
- $M$ は素数
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
$H$ $W$ $K$ $M$
出力
答えを出力せよ。
サンプル
サンプル1
入力
1 1 0 998244353
出力
499122177
$K=0$ のとき、緑の連結成分の大きさの $K$ 乗和は緑の連結成分の数に等しいです。
はるく君は、$\dfrac{1}{2}$ の確率で $0$ の、$\dfrac{1}{2}$ の確率で $1$ のうれしさを得ます。よって、期待値は $\dfrac{1}{2}$ です。
$499122177\times 2\equiv 1~(\bmod~998244353)$ なので、$499122177$ が答えです。
サンプル2
入力
3 1 1 998244353
出力
249561091
$K=1$ のとき、緑の連結成分の大きさの $K$ 乗和は緑のマスの数に等しいです。
サンプル3
入力
5 5 1000000000000000000 1000000007
出力
530357272
アドベントカレンダーといえば $5\times 5$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。