Matrix Exponentiation Optimization

Revision en1, by art-hack, 2020-02-12 19:31:28

Hey Everyone, So I saw this problem in one of the contests on Codechef(link)

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?

Tags #help, #matrix exponentialtion, complexity optimization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English art-hack 2020-02-12 19:32:18 2 Tiny change: 'tatement\nYou are ' -> 'tatement\n\nYou are '
en2 English art-hack 2020-02-12 19:31:52 19 Tiny change: 'CARR))\n\nYou are ' -> 'CARR))\n\nProblem Statement\nYou are '
en1 English art-hack 2020-02-12 19:31:28 4672 Initial revision (published)