Yes, it happens after Pisano period.
You may see the editorials of following problem for more details : https://www.hackerrank.com/challenges/emma-and-sum-of-products/editorial
You may see the editorials of following problem for more details about FFT : https://www.hackerrank.com/challenges/emma-and-sum-of-products/editorial
Can it be of any use in this question?? Or do you know any question which uses this property
I wrote Karatsuba with matrices as a coefficients, and my first implementation was running 4 minutes
Had to spend some time to improve it down to 3.5 seconds
I don’t think it is bad to have such a huge TL, unless naive solutions can pass.
Explained in this answer:
should be added to the editorial!
Thanks! Note that this solution is O(nk) and thus only gets 40 pts