Contest Duration: - (local time) (100 minutes) Back to Home
Official

## 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