@shubhu1596 I know this solution should not get AC but see that user is using midpoint formula of the line segment.Because there are n/2 lines, he could get n/10 points easily!
Well, My approach was to use O(N^3) brute force algorithm, coupled with a few observations, one being the same as official editorial. (Regarding Number of divisors)
Iāll try to post if i can, but no promise.
PS: Sorry for late reply
Yes, I even had more WAs on this problem alone than all other problems combined for this contest.
Only last day i used Modular Inverse that did the trick.
Maybe the excessive use of mod in block where t%2 != 1.
Canāt be sure because Iām not versed in python.
Yes, it can be labelled as easy-medium, If you get the obersvation.
One of my friend, rather better at coding than I am, didnāt even attempt this problem but solved all others (Partial in lucas, rest all 100). Only reason: He didnāt get these observations (due to geometry).
Thatās why i labelled it medium problem.
See the hidden part in editorial and read about modular multiplicative inverse.
Well, I had so many WAs in POINTPOLY trying to get the 30 point subtask- so many that I was afraid I will cross the 500 submission limit XD
For POINPOLY, i got 100 points in one go.
Frankly, i try to make as less submissions as possible. Otherwise, in longs of 2017, many problems had near 50 submissions of mine, with really minor differences (never reached 100 i guess).
Itās too an achievement, achieved by only a few 
For broken clock I used the formula :
cos (x+y)=2cos(x)cos(y)-cos(x-y). So when n is odd, it broke down to
cos(n/2+(n/2+1))=2cos(n/2)cos (n/2+1)-cos(1).
So I was saved from matrix expo., instead just a simple recursion worked, with just saving the already computed values in a map avoiding recalculation.
My POINPOLY solution is same as yours.
And yes, great editorials 
2 Likes
@cis_pie what about those cases in which the mid point of such chords are same, the code does not even checks for such duplicate points
Soā¦looks like I am the only one who made 0 observations and crashed the party with rand() XDDDD I solved this Q only because rand() got me 70 points :3
There might be other users too, still in shadows, remaining masked unlike you.
remaining masked unlike you
Ironically, in real life I prefer remaining masked. I just dont like any kind of spotlight lol.
It's too an achievement, achieved by only a few ;)
Trueā¦but I still wont prefer it in Cook-offs 
:3
Probably that N=10 case was the trump card and should have been included for 70 pts case also as a lot of random techniques passed for 70 pts.
They had more N=10 cases in the 70 point subtask. Thing is, the deadliest one wasnt the one they expected- the 30 point one turned out to be deadlier than rest.
But still, "Brute force for N \le100 and apply the ārandom techniqueā for other N would still pass. So, its ok. 70 points turned out to be boaster for people tbh :3
Thanks! @taran_1407 got that part.(Thanks to MITOCW)
But can you please tell how you formed the matrix for cos(nx),
means why f[0][0] = 2v and f[0][1] = MOD-1 (why even that -1)
and that return part??
func()
{
ā¦
1. F = new long[][]{{2v,MOD-1},{1,0}};
2. M = new long[][]{{2*v,MOD-1}, {1,0}};
3. power(N-1);
4. return mod(F[0][0]*v+F[0][1]);
}
And i am assuming that your power function works in the same manner, the power() and multiply() of method 4 of https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/
Hello Community,
Here is my first effort in making a editorial, and contributing to community.
Problem Link :https://www.codechef.com/FEB18/problems/PERMPAL
Please do have a look :
https://discuss.codechef.com/questions/122860/permpal-unofficial-editorial
1 Like