Hello Codeforces community, Recently I have started to notice that many solutions that I write are pretty slow, although it's always right solutions (they were intended by problemsetters). I've tried to look at code of red participants but didn't find any crucial difference in style of writing. There is one example of problem which I've tried to solve many times, but it didn't pass all the tests (due to TLE) http://codeforces.com/contest/719/submission/21066177 (the problem is http://codeforces.com/problemset/problem/719/E) Could you help me with it? If yes, please, could you tell me what makes my code so slow?
Thanks in advance for any help.
Your Code runs in O(nlg2)...Try to optimize it to O(nlg)...
Yeah, thanks, I see, but I didn't want to write memoization of matrix' degrees, because I'v seen the solutions that don't do it, but still runs in 2 ms. Maybe you can see some non-asymptotical slow moments?
Lots of my friends got tle with this solution too...(maybe all of them)
My suggestion is to don't try to get accept by this ways... You may change your code a little and get accept (for example your binpow function is recursive and has function-call, maybe your time decreases if you change it) but the goal is not to get accept verdict, it's to solve the problem...
Ok, I'll try to upgrade my code to O(n * lg n) Thanks for help!