How can I reduce the complexity of my code so that last subtask passes. Link to my code : https://www.codechef.com/viewsolution/17434010 asked 13 Feb '18, 23:38

The loop which is running for i =2 to t1 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. answered 13 Feb '18, 23:53
cos(N∗X)=2∗cos(X)∗cos((N−1)∗X)−cos((N−2)∗X). How can I solve this using matrix exponentiation
(14 Feb '18, 00:03)
Consider cos(nx) to be F(n). Therefore F(n)=aF(n1)F(n2), (where a=2cos(x)) this is a linear recurrence. Now this can be solved by matrix exponentiation. For matrix exponentiation goto this link. https://comeoncodeon.wordpress.com/2011/05/08/recurrencerelationandmatrixexponentiation/
(14 Feb '18, 00:07)
