Problem link: https://uva.onlinejudge.org/external/116/p11651.pdf . I know how to convert it to matrix exponentiation, On my solution the matrix is 77*77 size. as there are 200 test case and the matrix may be powered to 10^9 , It will case time limit exceed though O(n^3log(m)). How to make it time efficient ??

As far as I understand your solution work like this: you have some matrix

Aand vectorvwhich depend only on the base and you need to calculateA^{n}·vfor differentn. When you use fast exponentiation, you findA^{2k}for allkup to logarithm, multiply some of them and then multiply it byv. We can do the same, but in different order. Let's precalculate allA^{2k}. Now instead ofO(n^{3}) matrix multiplication we can useO(n^{2}) matrix by vector multiplication. We need to multiply matrices by vector, so time complexity is per query and for precalc.Btw why 77? I got 100 and i can optimize it to 50.

Sir , my solution may be wrong . Please explain your solution . I tried to solve reading a topcoder forum.

https://apps.topcoder.com/forums/;jsessionid=0CA65844DD4F4D178DAC03D867E65297?module=Thread&threadID=659037&start=0&mc=2#1177684 I didn't understand that totally. So i may be wrong . Sir please explain totally so that i can understand.

Denote by

cnt_{n, d}the number of ways to get the scorenif the last digit isd. Let's analyze the small case:d= 3. We have recurrence relations:cnt_{n, 0}=cnt_{n - 1, 1}+cnt_{n - 4, 2}cnt_{n, 1}=cnt_{n - 1, 0}+cnt_{n - 1, 2}cnt_{n, 2}=cnt_{n - 4, 0}+cnt_{n - 1, 1}.Do you know how to convert usual recurrence relation (like Fibonacci numbers) to matrix expo? Here we can do almost the same. Let's define a vector

v_{n}= (cnt_{n, 0},cnt_{n - 1, 0},cnt_{n - 2, 0},cnt_{n - 3, 0},cnt_{n, 1},cnt_{n, 2},cnt_{n - 1, 2},cnt_{n - 2, 2},cnt_{n - 3, 2}). These relations mean thatv_{n + 1}=Av_{n}for some matrixA, sov_{n}=A^{n}v_{0}.Sir, I know how to convert usual 1D recurrence relation to matrix (Like fibonacci). But it seems 2D, However I will try my best to convert it to matrix . But if i can not I will ask you.

If i can not do it and ask you please give me the answer.

Sir please answer me ,I have a problem . The matrix size is 100*100. How to optimize it ?? for last value 0 and 5 we have to keep 25 previous value each. . for last value 1and 4 we have to keep 16 previous value each. . for last value 2 and 3 we have to keep 9 value each. . so we have to keep total 25*2+16*2+9*2=100 value . . So matrix size is 100.

As there will be 200 test case and the power may be done upto 10^9 ,it will cause TLE.

You said you got 100 and optimized it to 50 , Then please explain. . . Another way you said is pre calculating. Ok i will precalculate all A^2^k matrix. But after that how it become O(n^2) ??

Let score =16, So I precalculate A^1,A^2,A^4,A^8 and A^16 . So if I need A^14 I have to do A^8*A^4*A^2 ,So where it has become O(n^2)??

Sir please explain both technique.

I will explain only the second technique. The first thing is just some non-asymptotic optimization, probably you don't need it to get AC.

You don't really need to find

A^{14}, you need to findA^{14}vfor some vectorv. So you can represent it in the formA^{8}(A^{4}(A^{2}v)). All multiplications are matrix-by-vector, they areO(n^{2}).Thanks sir , But the implementation seems too disgusting. for 5 different base I need 5 different vector, 5 different matrix , By the way thank you sir . I have learned many things from your comment. I can not give you something in return but I will pray for you.

Sir, At last I have solved it with 300+ line code.

Sir , What about the topcoder forums solution??

As far as I understand, solution from this forum also use matrix exponentiation, and matrix size is even more than in my solution, so I don't know how it can work fast without this trick.

Also you can read my code, it's much shorter than your. https://pastebin.com/8yeXvatX