题解：CF156E Mrs. Hudson's Pancakes

· · 题解

看了 ppip 的折半题解，确实很高明。

我来给一个暴力的做法，首先假设我们处理的进制是 b，我们可以处理一个 b+1 进制的数来表示问号，这个转移也是相当简单只需要枚举最后一个问号把他变成 [0,b-1] 即可。

当然这样做无法通过，在 b=2 的时候 3^{\log_2 n} 达到了约 5 \times 10^6，需要一点点小卡常。

如果你注意到了可以折半那就是 ppip 的做法，但是还有另外一种，注意到取模部分比较慢，可以尝试把几个模数做 lcm 之后再取模，这样就只需要大约 5 次就可以完成，至于询问，那个地方不是瓶颈所以可以随便实现。

code