問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$0$ で初期化されているカウンタがある.

に対して, 毎日時に以下を行う.
- $c_t={\tt T}$ のとき, $X$ % の確率で高橋君がカウンタを $1$ 増やす.
- $c_t={\tt A}$ のとき, $Y$ % の確率で青木君がカウンタを $1$ 増やす. ある日の $0$ 時直前からにこの一連の行動を始めるとする.　カウンタを $N$ にした人 (厳密には $N$ 回目にカウンタを $1$ 増やした人) が青木君である確率を求めよ.

制約

$1 \leq N \leq 10^{18}$
$1 \leq X,Y \leq 99$
$c_t~(0 \leq t \leq 23)$ は ${\tt T}$ または ${\tt A}$

解法

動的計画法で考える. ${\rm DP}[i,t ]$ をカウンタが $i$ になったのが $t$ 時である確率とする. このとき, $t=0,1, \dots, 23$ に対して, ${\rm DP}[N,t]$ を求めることができれば, 求めるべき確率は

$\displaystyle \sum_{\substack{0 \leq t \leq 23 \\ c_t={\tt A}}} {\rm DP}[N,t]$

である.

ベースケースを求めることにする. $i=0$ の場合であるが, $0$ 時直前からにこの一連の行動を始めたと問題にあるので, $23$ 時にカウンタが $0$ になったと考える. つまり,

${\rm DP}[0,t]=\begin{cases} 1 & (t=23) \\ 0 & (t \neq 23) \end{cases}$

である.

更新式について考える. カウンタが $(i-1)$ になったのが $t$ 時であるとき, カウンタが $i$ になるのが $u$ 時である確率を $p_{t,u}$ であるとする. このとき,

$\displaystyle {\rm DP}[i,u]=\sum_{t=0}^{23} p_{t,u} {\rm DP}[i-1, t]$

となる. ここで, $24$ 次正方行列 $P$ を $P=\left(p_{t,u} \right)_{0 \leq t,u \leq 23}$ とし, $\boldsymbol{a}_i~(0 \leq i)$ を

$\boldsymbol{a}_i:=\begin{pmatrix} {\rm DP}[i,0] \\ {\rm DP}[i,1] \\ \vdots \\ {\rm DP}[i,23] \end{pmatrix}$

とすると, $\boldsymbol{a}_{i+1}=P\boldsymbol{a}$ が成り立つ.

よって, $\boldsymbol{a}_N=P^N \boldsymbol{a}_0$ である. $P$ は $24$ 次正方行列であるから, $M:=24$ として, $P$ が求まっているという仮定の元では $P^N$ を行列累乗におけるダブリングによって $O(M^3 \log N)$ 時間で求めることができる.

最後に, $p_{t,u}$ を求める方法を考える.

カウンタが $(i-1)$ になったのが $t$ 時であるとき, カウンタが $i$ になるのが $u$ 時であるような場合について, $1$ 回目の $u$ 時でカウンタが $1$ 増える確率を $q_{t,u}$ とする. また, 1日 (24時間) カウンタが増えない確率を $r$ とする.

このとき, $1$ 回目の $u$ 時でカウンタが $k$ 増える確率は $r^{k-1} q_{t,u}$ である. そして, カウンタが $(i-1)$ になったのが $t$ 時であるとき, カウンタが $i$ になるのが $u$ 時であるような場合はこの $1$ 以上の整数 $k$ で表わすことができ, 唯一である. よって, $r \lt 1$ であるので,