y1s1，G和Ex在推等比数列式子上是相似的。
G
前置知识：BSGS（其实就是根号讨论）
首先我们展开这个递归式：
\[X_{i}\equiv A^{i} S+\sum_{j=0}^{i-1} A^j B \mod P \]感觉第一项有些难搞，故我们设\(F_{i}\)，为：
\[F_{i}\equiv A^{i+1} S+\sum_{j=0}^{i} A^j B \mod P \]之后我们套用BSGS的方法，设答案为\(kx+b\)。
则：
\[F_{kx+b}=A^{kx+b+1} S+\sum_{j=0}^{kx+b} A^j B=A^{kx} \cdot A^{b+1} S+\sum_{j=0}^{kx} A^j B+A^{kx}\sum_{j=1}^{b} A^j B \]提取公因式：
\[F_{kx+b}=A^{kx} ( A^{b+1} S+\sum_{j=1}^{b} A^j B)+\sum_{j=0}^{kx} A^j B \]我们先进行预处理：枚举\(i=0\)到\(\kappa -1\)，将 \(A^{i+1} S+\sum_{j=1}^{i} A^j B\) 模\(P\)的值存入map中，如果已经在map中有这个值了，那么我们取\(i\)最小的（因为我们要让答案最小）。
之后枚举\(x\)，查询\(\frac{G-\sum_{j=0}^{\kappa x} A^j B}{A^{\kappa x}} \mod P\)是否在map中，如果在，更新答案\(ans=\min (ans,\kappa x+C)\)，其中\(C\)是map中预处理得到的最小的值。
若我们设\(\kappa =70000\)，时间复杂度最优，大概是\(O(\sqrt n\log n)\)。
Ex
一道好题。
首先\(n\)个计数器是不好记录状态的。
一、简化并列出状态
我们设状态\(k=\max(A_{i}-C_{i})\)，其中\(C_{i}\)是第\(i\)个计数器的值。
可以发现，若\(k\leq 0\)，则我们就满足了\(C_{i}\geq A_{i}\)，并且，其实我们\(k\)在每次操作最多减去\(1\)，故当\(k=0\)时，我们就终止操作。
这样有什么好处呢？
转移是更方便的：
我们设\(r\)，满足\(A_{r}< k\leq A_{r+1}\)，则：
-
如果我们将第\(i\)个计数器清零，且\(i\leq r\)，那么\(k=k-1\)。（因为\(A_{i}\)<k，\(A_{i}-C_{i}\)也一定不超过\(k\)，此时\(k\)只能是由\(j>r\)的\(A_{j}-C_{j}\)转移而来）
-
如果我们将第\(i\)个计数器清零，且\(i > r\)，那么\(k=A_{i}\)。 （因为\(A_{i}\)>k，将第\(i\)个计数器清零后\(A_{i}-C_{i}=A_{i}>k\)，故此时\(k=A_{i}\)）
至此，我们发现\(k=\max(A_{i}-C_{i})\)，不仅减少状态数，并且转移还是简单的。
标签：AtCoder,kappa,sum,270,计数器,Ex,kx,我们 From： https://www.cnblogs.com/Nastia/p/16733697.html我们可以列出DP方程：\(F(k)\)表示状态为\(k\)时的期望操作次数，则\(F(k)=\frac{r}{n} F(k-1) + \frac{1}{n} \sum _{i=r+1}^{n} F_{A_{i}} + 1\)。