You can now upsolve the problems, you can find them under the "Tasks" tab, in the folder "HONI", and then you can select the year and the round.

Only the divisors of k are important and they are quite less.

You can solve it in a similar manner as the n^2 * k solution by dp(i, j, div) = the number of paths that end in cell (i, j) and gcd(path_product, k) = div. Notice that div is a divisor of k so the complexity narrows down to n^2 * max_number_of_divisors which should pass. The rest should be easy, but I can develop it further if you think it's needed. The answer is obviously dp(n, n, k).

The first observation is that if you want to increase the length of the shortest path in the graph by modifying exactly one edge you need to increase an edge that appears in all the shortest paths, so possible candidates for the solution are all edges that appear in all the shortest paths of the graph. You can check if an edge appears in all shortest paths by running Dijkstra 2 times from nodes 1 and N and also keeping track of the number of shortest paths from the source to some node, not just their length. This number can be very big, so you can keep it modulo some big prime number(for safety and avoiding collisions, you can use more modulo values; I used 4 but I don't know how many are necessary). Now you can check whether an edge appears in all shortest paths by some product of counts(computed with Dijkstra from 1 and N) in its endpoints and comparing that to the number of shortest paths also computed with Dijkstra.

Further, it's obvious that after you increase an edge of the shortest paths by 2, its new length will also increase by 2, not by 1, so the graph needs to initially have at least one path of length shortest_path + 1. If this is not the case, there is no solution and you print 0 and new line. After that, for all possible edge candidates you need to check if they lie in all paths of length shortest_path + 1. If so, you can not increase that edge, because after that you will no longer have a path of length shortest_path + 1 in the graph. Now this part seems similar to the first part computed with Dijkstra, but how exactly can you do that? Well my approach was to compute dp[node][0 / 1] and cnt[node][0 / 1] = the length and number of shortest paths from source to node such that their length % 2 == 0 / 1. You can do that with Dijkstra as I said earlier. In our problem it is required that the second shortest path of the graph is one unit longer than the shortest one, so it will have a different parity and be the smallest path with this property, so we can extract informations about it from dp and cnt tables(one of them will corespond to the shortest path and the other one to the second shortest). After that you use this tables to solve the problem as I described. Don't forget to compute cnt modulo something and use more modulo values for safety.

keep track of how many adjacent elements are ordered

While swapping values in the original array, maintain additionally: 1) an array with the indices of all the elements, and 2) a set of "bad" indices — all those that don't have a proper (x+1 modulo n) value next to it (i+1 modulo n).

See my code implementing that idea.