SUMSUMS summing sum - WA on cb and TLE on spoj

#1

Hi,

I have tried solving this problem with matrix exponentiation, on hackerblocks , I get one wrong answer for the following test case:
12 25
1000
1000000
99834332
9845323321
85633432
20003332
344223
908
32
21
44
9874342
and on spoj , I get a TLE after passing something like 14 testcases.
Here’s the link to my code: https://ide.codingblocks.com/s/72363

Please help me figure out what I am doing wrong. Thanks

#2

Hi you don’t have to apply matrix exponentiation (though it appears )
you have use mathematics to simplify the equations.
start with matrix exponentiation,some indirect maths is involved.

Hint: Use maths to simplify the equation

see my code https://ide.codingblocks.com/s/72427

#3

Got it! Thanks a ton!
One thing though, was using matrix exponentiation a bad idea? How do i make a choice when it comes to situations like these, cause matrix exponentiation seems very lucrative once i see the recurrence relation.

#4

Not a bad idea to matrix exponentiation, but many times it might not give you the answer.

To make a choice see the time complexity of your approach, calculate time complexity, if it is permissible then good to go, else you have do something else

#5

@tusharsk please help me in simpifying the equations, trying since long, not getting.

#6

Hi @tusharsk … I went through your code but I could not understand.
If possible, can you please explain your code? It would be a new learning for me.