Hey Everyone, So I saw this problem in one of the contests on Codechef(link)
Problem Statement
You are given two integers N and M. Find the number of sequences A1, A2,…,AN, where each element is an integer between 1 and M (inclusive) and no three consecutive elements are equal. Since this number could be very large, compute it modulo 109+7.
So I used my general code for Matrix Exponentiation but got a TLE.
My submission
People have used matrix exponentiation for the same and got a full score.
Selected submission
Things that I have tried already are
- Switching ll with int
- Reserving the size of the vector already.
Please tell me what I can optimize more in my code so that we do not face this problem in any of the Matrix Exponentiation problems?
Modulo is a costly operation and in your multiply function and at some other places you have used unncessary modulo
(a % mod + ((b % mod)*(c % mod)) % mod
which can be replaced with(a + (b * c) % mod) % mod
(sincea,b,c
are long long. In case they are not long long typecast them).+1
even more, just
(a + b * c) % mod
is enoughI tried that both ways, it gets WA and the TLE remains
Not-Afraid's Way https://www.codechef.com/viewsolution/29577879
Errichto's Way https://www.codechef.com/viewsolution/29577950
Well, you have somebody's correct code so you can easily test your solution locally against it. And compare running time too.
I don't know about WA (maybe your implementation of matrix expo or something else has some bug) but the things creating TLE are:
1)
Instead of using endl use '\n'
2)
Pass vector with reference as someone mentioned below.
Thanks a lot Errichto and Not-Afraid for your points, there was a minor bug that I removed from your solution and got AC.
Click
P.S. Thanks for the tip that '\n' is faster than endl.
You are passing Vectors by value. Pass them by reference and it should solve the problem.
Does creating a vector and then passing it using its reference have such a significant impact over just passing it?.
yes, everytime you call a function, you make unnecessary copies of it.
Passing without reference creates a new copy of vector every time while this is not the case with reference . So yes it has a significant effect.
Thanks, that did make the difference.