10766 - Organising the Organisation

[Per]

It is a small mistake from my side that the problem is solvable using long doubles, I never thought to make sure that that wouldn't work. Bigints are highly likely to give you TLE, and regular doubles have no way of handling the precision required.

But anyway, all ways that work are good ways.

[..]

Hi Per, I used long double because I have no idea how to solve it using integer arithmetic. I have considered using Chinese Remainder Theorem(as Cho said in previous post) + BigInt to solve this problem, but it is too troublesome. (In the other way, I am too lazy )
May I know what is the expected approach to solve the problem??

[little joey]

An "infinite precision" rational number class (analogus to a bigint class for natural numbers) would solve this problem without the "hope and pray" imprecision of (long) doubles. But there is no problem in the set (AFAIK) that requires it, so I haven't got one yet. Guess I'm too lazy to make one without the nessecity of using it in a program...

[Per]

My "intended" solution was to compute the answer modulo a prime bigger than 10^15. There is no need for CRT or BigInts, just regular modular arithmetic (including inverse).

A rational-based solution would probably get TLE (or well, at least the one I wrote is way too slow).

[Cho]

But the multiplication (involved during computing the determinant modulo a prime bigger than 10^15) could exceed the limit of long long before you do the modulation.
How could you handle that?

[Per]

One can use a simple double-and-add algorithm for multiplication (analogous to square-and-multiply for exponentiation).