lc1622 Fancy Sequence

By | December 5, 2020
Share the joy


at [2],

From [0] to [2], adding change operation of +a, +b, *c, +d, it needs apply [0]*mult + add



Reversely, from [2] to [0], to calculate back with +a, +b, *c, +d, it needs apply ([2] – add) / mult


In all, the calculation is like when appending each value, calculate back by removing the operations before. Let it start from very beginning without any operation. Then in the end after all operations,  when getIndex, calculate forwardly with current mult, add

(a / b) % mod = (a * x) % mod

Here, x is inverse modular of b. In Java,

x = BigInteger.valueOf(a).modInverse(BigInteger.valueOf(mod)).longValue();