题解 P3306 【[SDOI2013]随机数生成器】

· · 题解

在下以优秀的代码长度以及手写hash在BZOJ/luogu上光荣上榜！最优解前两个都是我哒，第一名是开了O2，第二名是没开O2 ╮(╯▽╰)╭

题目让求 X_{i+1}=aX_i+b\ (mod \ \ p)

我们回忆一下数学必修五关于数列的内容，把ta化成一个等比数列是不是好做很多呢？

那么我们画出来的等比数列就是

X_{i+1}+\frac{b}{a-1}=a(X_i+\frac{b}{a-1}) \ (mod\ p)

那么根据等比数列递推公式X_n+\frac{b}{a-1}=a^{n-1}(X_1+\frac{b}{a-1}) \ (mod\ p)

这里只有a^{n-1}是未知的呀，我们移项

a^{n−1}≡(X_n+b∗inv(a−1))∗inv(X_1+b∗inv(a−1))\ (mod\ p)

然后就是一个裸的BSGS啦

不过要特别注意特判内容，a=0和a=1，这个柿子都没有意义，所以要特判

更加优美的画柿子过程+优美代码戳这里