I found two C# solutions: with multithreading — Accepted and without multithreading — TLE. The author of the solution uses Parallel.For in the functionMultiplyMatrixPow, due to which it achieves success. Question: how many cores can we load on codeforces servers when testing our solution?
UPD: In first program author takes remainder from integer division 3 times, in second program just 1 times. So, this is not multithreading hack.
Look at mike's comment: blog.
Thanks, it turns out that additional cores are not used to run the program.
But why use of the parallel for speed up the solution? Are there any optimizations in comparison with the usual cycle for?
As far I know, you'll never decrease the running time on all adequate e-judges via additional threads, since they're single-cored. Your case is probably false-positive, I mean when I was writing solutions on C#, it could give different execution time on the server, and your code may give a result somewhere in an interval [2000-x, 2000+x] of milliseconds, almost randomly.