题解：AT_abc271_g [ABC271G] Access Counter

· · 题解

题面

考虑记 f_{i,j} 表示当前已经有 i 次访问，且第 i 次访问存在于第 j 个小时。

那么下一次访问在第 k 个小时的概率是什么呢？

枚举中间隔的天数，假设从第 j 个小时第一次到第 k 个小时中间经过的小时都没有访问网站的概率为 P_{j,k}，一天没有发生访问的概率为 P，那么我们的转移系数为：

s_{j,k}=\sum_{i=0}^{\infty }P^kP_{j,k}=\frac{P_{j,k}}{1-P}

接下来把转移写成矩阵，做矩阵快速幂即可。

令 m=24，则时间复杂度为 O({m}^3\log{n})。