TLE in two test cases

#1

what is wrong with the code https://ide.codingblocks.com/s/226212

#2

You need to use Matrix Exponentiation method for answering the queries efficiently.

#3

i used code force hack method same time complexity as matrix exponentiation

#4

Sorry, but I think matrix exponentiation will work. Try it. I don’t know about this method you used although.

#5

this method is in course content and derived from matrix exponent
it is same as matrix exponent but less numbers of code lines.

#6

Take hashmap as global or pass it by reference. The current way makes it copy itself for the function call which consumes a good amount of time.

#7

still getting tle https://ide.codingblocks.com/s/226739

#8

I submitted your code in C++ using unordered_map and fast i/o and it got accepted.
So, try doing the same in Java.
Everything apart your code works with proper stl in c++.

#9

still getting tle after applying faster input output class

#10

Then it might be that there are stricter time limits for JAVA or its i/o or hash map aren’t as fast as they are in c++, as the same code got accepted in c++.

#11

getting tle using matrix exponentiation https://ide.codingblocks.com/s/235825

#12

Hey @mayank10
As you rightly said and the TA as well that matrix exponentiation won’t be able to pass these test cases
You need to use the derived formula along with hashmaps to memoise
Please implement that and see the result