Modular operations are expensive. And even if they weren't, the first solution already took nearly 2s and adding more operations there inside the loop would yield TLE.

It's not a random guessing problem. Notice that the difference is between 1 and $$$n^2-1$$$, so naturally we first try to get them all. For $$$n^2-1$$$, $$$n^2$$$ and 1 need to be adjacent, then for $$$n^2-2$$$, either $$$n^2$$$ and $$$2$$$ or $$$n^2-1$$$ and $$$1$$$ need to be adjacent, .... It's quite easy to achieve that. If you know gray code, Z-order, or something like those, easier.

You can calculate the inverses of factorials more efficiently by calculating them from n to 0.

Wow.. That was the reason I couldn't get AC. I thought I could choose the order of operations.

1 1 100 10 -> ... -> 100 100 100 10 -> ... -> 100 100 100 100

There was hardly any implementation before E ...

I have no idea how to interpret dp when you put k in the inner loop. In Floyd-Warshall, k represents the intermediate vertex, i.e., the algorithm updates dp when it finds a shorter path passing through k.

Wow... I was thinking and thinking with that misunderstanding of the first operation for the whole contest. I got to read the statement a bit more carefully.

Oh, I see the issue now. You are not using std::abs. Either use std::abs or llabs.

I guess the round could have been better if the problem E had an easier version with lower constraints...

I don't know, my submission got passed just fine with abs.

minu = m % MOD. But seriously, the diagnostics message is already pointing the exact problematic line in this case. It doesn't make sense that you can't debug this.

That is not even a valid placement of cacti. Probably the issue of most WA submissions was one-directional dp, while we needed bfs.

Change n, m, ans, etc to long long, then I guess it will be fine. What about wiki page? https://en.wikipedia.org/wiki/Modular_arithmetic Or you can just read the intro section of any elementary number theory book.

Thanks a lot.

No, you are still multiplying by m/2. You need to do minu *= (m/2)%MOD; minu %= MOD. In the end, you also need ans %= MOD before if(ans<0)

The issue is the range of m. For example, you multiply by m/2. Use (m/2)%MOD instead.

Yeah, I tried many examples for last 30 mins but couldn't really figure out the counter example. I wish I could see the test 2 now...

So cool E and F!

Yeah, I was quite smiling when I read FTL :)

Well, your logic needs extra 0 at the end of s.

Assuming you meant to fail to solve any problems, knowing arrays, sortings, and elementary maths is usually enough for first problems.