I solved it using a function similar to modular exponentiation. \cos tx = 2\cos^2(t/2) - 1 for even t \cos tx = 2\cos(\lfloor t/2 \rfloor) \cos(\lceil t/2 \rceil) - \cos x for odd t
Simple recursive function with memoization passes. Though I couldn’t derive an upper bound on number distinct recursive calls. I guess its around 2 * \log t.
Can someone help me understand the formula manipulation to get from the first matrix representation of the formula to the second one with the second 2x2 matrix raised to the (t-1) power?
I calculated cosnx by breaking n into a sum of powers of 2 and then calculated each power recursively using the formula cos2x=2cos^2-1. I used memoization to avoid repeating the same calculations. This required no more than log(n) operations.
To combine the powers of 2, I used the formula cos(a+b)=2cos(a)cos(b)-cos(a-b). I also used memoisation in this approach by mapping the previously calculated values of cosx otherwise it would result in TLE.
hey everybody,
I found the x correctly. using cos(x) = d/l;
now why does doesn’t we get the final length by cos(x*t) this can +ve or -ve depending on the quadrent.
I believe cos will take care of everything as it changes the quadrent it switched the sign of value i.e from -ve to +ve or vice versa.
Please confirm… my broken code is https://www.codechef.com/viewsolution/17355814
There is no need to use matrices or trigonometry at all. In my solution, all you need to know is how to deal with complex numbers.
First, swap X and Y coords for convenience. Then, we have complex number (d/l, sqrt(1-(d/l)^2)). Note, that real part of its Nth power times l is the answer, according to properties of complex number multiplication. But its imaginary part is irrational, how do we tackle that?
Let’s denote that nasty root sqrt(1-(d/l)^2) as R. Take a look at what happens when we multiplying complex numbers that looks like (a, b*R):
As we can see, field of numbers of that kind is closed under multiplication. So, all we need is to store complex number (a, b*R) as a pair of integers (a, b), write our own multiplication function, and use binpow.
When I use the normal iterative to compute the chebyshev and fermat’s little theorem for modular inverse,
I get wrong answer on the first subtask.
The given test cases are computed right tho, and yes, I need something better for when t is large
but could someone tell me what’s wrong in this code, at least for t <= 3?
@albert it is possible that multiplying the two values may result in integer overflow. Hence after multiplying two values take mod, and then multiply with third value.