## G - Access Counter Editorial by en_translator

### Finding the probability that the \(1\)-st access is made at \(0\), \(1\), \(\ldots\), and \(23\) o’clock

If \(N=1\), it is sufficient to find the probability that the \(1\)-st access is made at \(0\), \(1\), \(\ldots\), and \(23\) o’clock and find the sum over those corresponding to Aoki’s, but some of you may feel this is already difficult. That is, the desired value is \(\sum_{i=1}^{\infty } p_i\) where \(p_i\) is the probability that the \(1\)-st access is made at say \(0\) o’clock on the \(i\)-th day, but we cannot find the sum of the infinite number of values with a for statement. Instead, we need a mathematical transformation.

Let \(q\) be the probability that there is no access at \(0\), \(1\), \(\ldots\), and \(23\) o’clock. Then, \(p_i = q^ip_1\), so \(\sum_{i=1}^{\infty } q^i p_1=(\sum_{i=1}^{\infty } q^i )\times p_1\). By the constraints, we have \(q<1\), so we have \(\sum_{i=1}^{\infty } q^i =\frac{1}{1-q}\) by the formula of the sum of infinite geometric series, and thus we can express the probability that the \(1\)-st access is made at \(0\) o’clock as \(\frac{p_1}{1-q}\). Same applies for the other time.

By the way, we can check exhaustively that \(q \neq 1\) modulo \(998244353\) under the constraints.

### \(\mathrm{O}(N)\) solution

Let \(\mathrm{dp}_{i,j}\) be the probability that the \(i\)-th access is made at \(j\) o’clock on the \(i\)-th day. Since the discussion above is equivalent to the probability that the next access is at \(0\), \(1\), \(\ldots\), and \(23\) o’clock when the last access is made at \(23\) o’clock. We can find similarly when the last access is made at \(0\), \(1\), \(\ldots\), and \(22\) o’clock. How can we optimize it?

### \(\mathrm{O}(\log N)\) solution

Let \(\mathrm{dp}_{i,j,k}\) be the probability that the \(2^i\)-th access is made at \(k\) o’clock when the last access is made at \(j\) o’clock. \(i=0\) can be solved by the discussion above, and \(i\geq 1\) can be found as \(\mathrm{dp}_{i,j,k} = \sum_{l=0}^{23} \mathrm{dp}_{i-1,j,l} \times \mathrm{dp}_{i-1,l,k}\). Therefore, we can use fast exponentiation trick to find the answer for \(N\), for a complexity of \(\mathrm{O}(\log N)\).

Note that this is equivalent to finding the \(N\)-th power of a matrix where the columns and rows correspond to \(j\) and \(k\), respectively. Since the optimization of \(\mathrm{dp}\) using matrices are often seen, we recommend you to learn it.

Exercises from the past problems:
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: