seems like dp, but could not solve it. any ideas?

I used dp, with the following observations:

• Consider the sequence of column maximum values (of a correct ordering). It is obvious that it should be a sequence of distinct numbers, and permuting them (by swapping the columns) yields a different ordering. Therefore it's sufficient to consider the sequence as non-decreasing (adding the columns from left to right), and multiplying the answer with n!.

• Same as above for the rows' maximum values. With the two observations, we can safely fix number 2n - 1 on the top-left cell, and multiply the answer with 2 × n!. This also makes sure one of the columns' condition is fulfilled, and we only have to care about the other column.

• We have the following dp f(i, j, k) — the number of correct ordering with i columns having at least one number, j columns having two numbers, and k — whether the second column's condition has been satisfied — calculated by adding the numbers one by one, from the largest to the smallest. Obviously f(1, 0, 0) = 1 (we put the number 2n - 1 in).

• State transformation is as follow:

• If i < n, we can put the next number onto the leftmost empty column.

  • If we put the number onto the first row, we move to (i + 1, j, k): f(i + 1, j, k) +  = f(i, j, k).
  • If we put the number onto the second row, we have to check whether the second row's condition has been fulfilled. If it already has, the next number's position does not affect the sequence, so we do not move to the next state since the above case has already covered it. If not, we could move to the next state (i, j, (nextNumber >  = K)): f(i, j, (nextNumber >  = K)) +  = f(i, j, k).

• If (j < i), we can put the next number onto a column with one number. Note any ordering of second-numbers does not affect the sequence, so f(i, j + 1, k||(nextNumber >  = K)) +  = f(i, j, k). You may ask why the condition check was included: Since any ordering of the second-numbers are the same, we could use a greedy approach to try creating a correct ordering, by moving the largest second-number to the second row of the first column (the one with number 2n - 1 above).

This should create a O(n²) solution, with the answer being f(n, n, 1) * 2 * n!

The number of possible graphs contains a directed path from u to v is 2^(N — 1 — distance(u, v)). The sum of this value for all ordered pairs (u, v) is the answer. Then we can use dfs to calculate it in O(N)

Another solution: Suppose that we choose the direction of each edge at random. We want to compute expected value of the random variable: #{directed paths}.
Let us choose a root. In each node v we remember three values:

1. In[v] = Expected number of nodes w in subtree of v s.t. there exists path w → v

2. Out[v] = Expected number of nodes w in subtree of v s.t. there exists path v → w

3. Ans[v] = Expected number of paths w₁ -  > w₂ such that w₁, w₂ are in subtree of v and this path goes through v.

One can observe that :

One can observe that In[w] = Out[w] and

.

So we can compute those values in O(N) by simple dfs. The final answer is .

if n % 2 ≠ 0 we can choose 2, 4, .., 2·k.

if n % 3 ≠ 0 we can choose 3, 6, .., 3·k.

if n % 4 ≠ 0 we can choose 4, 8, .., 4·k.

if n % 5 ≠ 0 we can choose 5, 10, .., 5·k.

if n = 60 we can choose 7, 14, 21, .., 98, 1.

In general for any N, you can choose a number x other than 1 such that gcd(N, x) = 1 After choosing x, you can simply generate it's multiples. However there is a corner case(s):
N being 1,
N being 60 or 90 and L = 15 which you need to take care of.