变色龙的太空之旅

zoxx · 2018-08-26 22:24:57 · 个人记录

题目

有n只变色龙，分别向右爬行或向左爬行，若左右颜色分别为a,b，左边碰到右边的变色龙后不变，右边碰到左边的变色龙后变成(a+b)mod k，问所有变色龙颜色为j的时间和(n<=100000)

题解

显然我们可以发现，对于从左向右走的变色龙，肯定保持的是同一种颜色，所以我们可以直接将这一部分计算出来，而对于从右向左走的变色龙，如果我们不考虑取模，那这就是一个递增的过程，而这并不好处理。我们可以直接考虑所有b的和，发现我们可以直接记录下所有的前缀和，这显然是从左向右递增的，我们哪所有的总和减去它，就是在每一个位置的颜色了。把每一种颜色的贡献都事先预处理出来，在计算结果时将其扫一遍就可以了，即

最后还要加上变色龙在碰到了所有向右走的龙后余下的路程，只要加上0.5*d就可以了