G - Access Counter Editorial by m_99
\(1\) 回目のアクセスが \(0,1,\ldots,23\) 時である確率を求める
\(N=1\) の場合、\(1\) 回目のアクセスが \(0,1,\ldots,23\) 時である確率を求めてそのうち青木君のアクセスに対応するものの総和を求めれば良いですが、人によってはこの時点で難しいと感じるかもしれません。というのも、\(1\) 回目のアクセスが \(i\) 回目の \(0\) 時になる確率を \(p_i\) とすると求めたい値は \(\sum_{i=1}^{\infty } p_i\) になるのですが、無限個の値の和をfor文などで求めるわけにはいかないためです。対処法として、数学的な式変形等を行う必要があります。
\(0,1,\ldots,23\) 時にアクセスが発生しない確率を \(q\) とします。すると、\(p_i = q^ip_1\) となり、求めるべき値は \(\sum_{i=1}^{\infty } q^i p_1=(\sum_{i=1}^{\infty } q^i )\times p_1\)となります。制約より \(q<1\) であることに注意すると、無限等比級数の和の公式より \(\sum_{i=1}^{\infty } q^i =\frac{1}{1-q}\) となり、これを用いて \(1\) 回目のアクセスが \(0\) 時である確率を \(\frac{p_1}{1-q}\) と表せます。また、他の時刻についても同様です。
なお、\(\mathrm{mod}\) \(998244353\) で\(q \neq 1\) となることは制約の範囲内で全探索をすることで確認出来ます。
\(\mathrm{O}(N)\) 解法
\(\mathrm{dp}_{i,j}\) を \(i\) 回目のアクセスが \(j\) 時である確率とします。前述の議論は最後のアクセスが \(23\) 時だった場合に次のアクセスが \(0,1,\ldots,23\) となる確率を求めるということに等しく、同様に最後の時刻が \(0,1,\ldots,22\) 時の場合についても次のアクセスの確率を時刻ごとに求められます。これを高速化します。
\(\mathrm{O}(\log N)\) 解法
\(\mathrm{dp}_{i,j,k}\) を、最後のアクセスが \(j\) 時の状態から始めて \(2^i\) 回目のアクセスが \(k\) 時である確率とします。\(i=0\) のものについては前述の議論より求められ、\(i\geq 1\) の場合は \(\mathrm{dp}_{i,j,k} = \sum_{l=0}^{23} \mathrm{dp}_{i-1,j,l} \times \mathrm{dp}_{i-1,l,k}\) と求められます。これを用いると繰り返し二乗法で \(N\) に対する答えも求められ、計算量が \(\mathrm{O}(\log N)\) になります。
なお、これは行が \(j\) 、列が \(k\) にあたる行列の \(N\) 乗を求めることに等しいです。行列の累乗を用いた \(\mathrm{dp}\) の高速化はよく出題されるため、慣れておくと良いでしょう。
過去の出題例
https://atcoder.jp/contests/dp/tasks/dp_r
https://atcoder.jp/contests/abc256/tasks/abc256_g
https://atcoder.jp/contests/abc129/tasks/abc129_f
posted:
last update: