Broken Clock last subtask

general
, ,
1

How can I reduce the complexity of my code so that last subtask passes. Link to my code :-
https://www.codechef.com/viewsolution/17434010

2

The loop which is running for i =2 to t-1 should be removed, and matrix exponentiation can be used, which reduces complexity to O(log t).
cos(N∗X)=2∗cos(X)∗cos((N−1)∗X)−cos((N−2)∗X), this can be solved by matrix exponentiation.

1 Like
3

cos(N∗X)=2∗cos(X)∗cos((N−1)∗X)−cos((N−2)∗X). How can I solve this using matrix exponentiation

4

Consider cos(nx) to be F(n).
Therefore F(n)=aF(n-1)-F(n-2), (where a=2cos(x)) this is a linear recurrence. Now this can be solved by matrix exponentiation.
For matrix exponentiation goto this link.