I tried solving problem 321C — Ciel the commander with centroid decomposition. I think thats what many people did and got an AC with, but my submission got a TLE. Could anyone tell me why did it exceed the time limit?

It's the same knight's tour problem (since the problem is in Vietnamese i wont put a link to the original one):

We have a chessboard of size a*a, the knight's coordinate is x, y. We have to find the longest path of the knight (the maximum number of squares the knight can go through), without having the knight going through a same square twice. Note that it does not have to be a close tour. I used the recursion method (i do considered breaking the operation when there exist a path that covers all a*a squares, too) and finds out that it only works well for a <= 50 (however, occasionally is passes the time limit).

But the limit is fairly larger (a <= 500), which — of course, got me 3 TLEs (here)

So instead i just tried printing a*a, and the 3 tests that i got TLE verdict before now return AC, but its wrong for the other 7 tests. (here)

So lastly i tried this

if(a>50)
{
    cout<<a*a;
    return 0;
}

and it got all AC for the 3 TLE tests but WA for 2 of the initially right ones (here)

Here's the code of the submission that got 70 points

Appreciate all helps.

Theres a problem from the The ICPC 2018 — Vietnam Central Provincial Contest that supposedly involves some combinatorics (The problem is here)

I originally planned to count the ways to break N/K into sum of at most M numbers, and then count the number of permutations of the children for each ways, and then use binpow to calculate total_ways % 1e9+7 (probably the first thing you would think of when you see the problem). But the limit was so high that i will have to choose between ridiculously long running time or using bignum (which can cause either TLE or MLE, whatever comes first.)

So it would be better if i could have an O(1) or an O(log N/K) solution for this problem.

Thanks.

Edit: the editorial is 4 pages long and it is in Vietnamese, and i don't understand it either