Задача . Tree Depth

Чтобы сгенерировать это BST, ФД начинает с перестановки \(a=\{a_1,a_2,\ldots,a_N\}\) целых чисел \(1\ldots N\), где \(N\le 300\). Затем он выполняет следующий псевдокод с аргументами \(1\) and \(N\).

generate(l,r):
  if l > r, return empty subtree;
  x = argminl <= i <= r ai; // index of min ai in {al,...,ar}
  return a BST with x as the root, 
    generate(l,x-1) as the left subtree,
    generate(x+1,r) as the right subtree;

Например, перестановка \(\{3,2,5,1,4\}\) сгенерирует такое BST

    4
   / \
  2   5
 / \ 
1   3

Пусть \(d_i(a)\) обозначает глубину вершины \(i\) в дереве, соотвествующем \(a\), то есть количество вершин на пути из \(a_i\) к корню. В примере выше, \(d_4(a)=1, d_2(a)=d_5(a)=2,\) and \(d_1(a)=d_3(a)=3\).

Количество инверсий \(a\) равно количеству пар целых чисел \((i,j)\), таких что \(1\le i<j\le N\) и \(a_i>a_j\). Коровы знают, что \(a\), которую ФД использовал для генерации BST, имеет ровно \(K\) инверсий \((0\le K\le \frac{N(N-1)}{2})\). Среди всех перестановок \(a\), удовлетворяющих этому условию, вычислите Остаток, когда \(\sum_ad_i(a)\) поделено на \(M\) для каждого \(1\le i\le N\).

1 2 3