How can I reduce the complexity of my code so that last subtask passes. Link to my code :-

https://www.codechef.com/viewsolution/17434010

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

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

Consider cos(nx) to be F(n).

Therefore F(n)=a*F(n-1)-F(n-2), (where a=2*cos(x)) this is a linear recurrence. Now this can be solved by matrix exponentiation.

For matrix exponentiation goto this link.