lc1622 Fancy Sequence

By | December 5, 2020
0 Comment
Share the joy
  •  
  •  
  •  
  •  
  •  
  •  

fancy1

at [2],
mult=c
add=((a+b)*c+d)

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

 

fancy2

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();

https://www.bilibili.com/video/av970029359/