Actually this happened with me during the contest, i was getting cos(60) as 0.4999999999999999 and using Fraction if u convert it in p/q form then p comes as 4503599627370495 and q comes as 9007199254740992. p*(q^-1) comes out to be 879237148. It makes a huge diff to our ans. Actually if u do mod 360 still values will be rounded. It can give us wa.
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):
(a+b*R*i) * (c+d*R*i) = (a*c-b*d*R*R) + (ad+bc*R)*i = (a*c-b*d*(1-d/l)) + (ad+bc)*R*i
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.
[1]
[1]: https://www.codechef.com/viewsolution/17300590This is identical to the tester’s solution, only interpreted as complex numbers.
1 Like
It just follows from plain matrix multiplication. Any linear recurrence can solved in this manner using matrix exponentiation. You can find relevant tutorials on the internet.
Maybe you need glasses?
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?
Looks good enough to me. Way better than previous editorials.
There is other way to solve the question. Below is my approach:
We know e^ix = cos(x) + isin(x)
=> e^inx = cos(nx) + isin(nx)
We know cos(nx) + isin(nx) = (cos(x) + isin(x))^n
After computing we would have cos(nx) = real((cos(x) + isin(x))^n)
The multiplication can can be done in logn.
Here is the code: https://www.codechef.com/viewsolution/17348197
@manjuransari at one place u used the line
t_x = (xn_x)%mod - ((((y_xn_y_x)%mod)*diff)%mod)%mod;
cant we write it as t_x = [(xn_x)- ((((y_xn_y_x))*diff))]%mod;
i.e after multiplying all the values at last we are calculating mod
why using mod everytime as question clearly mentions you have to give FINAL result as ans%mod
why using mod every time will not affect our answer
pls someone help
@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.
Mine was exactly same as well
i used binomial coefficients but iam getting wrong answer for some subtasks
If t=1, we return cos(tx)=(cos(x),0)and sin(tx)=(0,1);
Can anyone tell me why we are initializing sin(tx)=(0,1) ?
Maybe because you guys easily solved the problems.
For a newbiew, it should be stated why do we actually need matrix-expo here.
Can anyone please explain one example of this problem along with modular inverse calculation.
What is the problem if i do the following :
- \theta = \arccos(d/l)
- in order to find \cos(t* \theta), i find the equivalent form of t*theta as (k*2*pi + x) and compute \cos(x)*l to get the required y.
I find x as x = t* \theta - (int)(t* \theta/ \arctan(1)*8)* \theta
Is the problem due to floating point airthematic ?
Hello ‘d’ is opposite side right?‘l’ is Hypotenuse right?