Решение требует пояснений. Обозначим количество перестановок с n элементами, имеющими ровно k инверсий, через I (n, k).

Теперь I (n, 0) всегда равно 1. Для любого n существует одна и только одна перестановка, которая имеет 0 инверсий, т.е. когда последовательность все более сортируется.

Теперь I (0, k) всегда равно 0, так как у нас нет самой последовательности

Теперь, чтобы найти I (n, k), давайте рассмотрим пример последовательности, содержащей 4 элемента {1,2,3,4}

для n = 4 ниже перечислены перестановки, сгруппированные по количеству инверсий.

|___k=0___|___k=1___|___k=2___|___k=3___|___k=4___|___k=5___|___k=6___|
| 1234    | 1243    | 1342    | 1432    | 2431    | 3421    | 4321    |
|         | 1324    | 1423    | 2341    | 3241    | 4231    |         |
|         | 2134    | 2143    | 2413    | 3412    | 4312    |         |
|         |         | 2314    | 3142    | 4132    |         |         |
|         |         | 3124    | 3214    | 4213    |         |         |
|         |         |         | 4123    |         |         |         |
|         |         |         |         |         |         |         |
|I(4,0)=1 |I(4,1)=3 |I(4,2)=5 |I(4,3)=6 |I(4,4)=5 |I(4,5)=3 |I(4,6)=1 |
|         |         |         |         |         |         |         |

Теперь, чтобы найти количество перестановок с n = 5 и для всех возможных k, мы можем вывести рекурсию I (5, k) из I (4, k), вставив n-й (самый большой) элемент (5) где-нибудь в каждой перестановке в предыдущие перестановки, так что результирующее число инверсий равно k

например, I (5,4) - это не что иное, как количество перестановок последовательности {1,2,3,4,5}, каждая из которых имеет ровно 4 инверсии. Давайте теперь посмотрим I (4, k) наверху, пока столбец k = 4, количество инверсий будет ‹= 4 Теперь давайте разместим элемент 5, как показано ниже.

|___k=0___|___k=1___|___k=2___|___k=3___|___k=4___|___k=5___|___k=6___|
| |5|1234 | 1|5|243 | 13|5|42 | 143|5|2 | 2431|5| | 3421    | 4321    |
|         | 1|5|324 | 14|5|23 | 234|5|1 | 3241|5| | 4231    |         |
|         | 2|5|134 | 21|5|43 | 241|5|3 | 3412|5| | 4312    |         |
|         |         | 23|5|14 | 314|5|4 | 4132|5| |         |         |
|         |         | 31|5|24 | 321|5|4 | 4213|5| |         |         |
|         |         |         | 412|5|3 |         |         |         |
|         |         |         |         |         |         |         |
|    1    |    3    |    5    |    6    |    5    |         |         |
|         |         |         |         |         |         |         |

Каждая из приведенных выше перестановок, содержащих 5, имеет ровно 4 инверсии. Таким образом, общая перестановка с 4 инверсиями I (5,4) = I (4,4) + I (4,3) + I (4,2) + I (4,1) + I (4,0) = 1 + 3 + 5 + 6 + 5 = 20

Аналогично для I (5,5) из I (4, k)

|___k=0___|___k=1___|___k=2___|___k=3___|___k=4___|___k=5___|___k=6___|
|   1234  | |5|1243 | 1|5|342 | 14|5|32 | 243|5|1 | 3421|5| | 4321    |
|         | |5|1324 | 1|5|423 | 23|5|41 | 324|5|1 | 4231|5| |         |
|         | |5|2134 | 2|5|143 | 24|5|13 | 341|5|2 | 4312|5| |         |
|         |         | 2|5|314 | 31|5|44 | 413|5|2 |         |         |
|         |         | 3|5|124 | 32|5|14 | 421|5|3 |         |         |
|         |         |         | 41|5|23 |         |         |         |
|         |         |         |         |         |         |         |
|         |    3    |    5    |    6    |    5    |    3    |         |
|         |         |         |         |         |         |         |

Таким образом, общая перестановка с 5 инверсиями I (5,5) = I (4,5) + I (4,4) + I (4,3) + I (4,2) + I (4,1) = 3 + 5 + 6 + 5 + 3 = 22

So I(n, k) = sum of I(n-1, k-i) such that i < n && k-i >= 0

Кроме того, k может увеличиваться до n * (n-1) / 2, это происходит, когда последовательность сортируется в порядке убывания https://secweb.cs.odu.edu/~zeil/cs361/web/веб-сайт/Лекции/вставка/страницы/ar01s04s01.html http://www.algorithmist.com/index.php/SPOJ_PERMUT1

#include <stdio.h>

int dp[100][100];

int inversions(int n, int k)
{
    if (dp[n][k] != -1) return dp[n][k];
    if (k == 0) return dp[n][k] = 1;
    if (n == 0) return dp[n][k] = 0;
    int j = 0, val = 0;
    for (j = 0; j < n && k-j >= 0; j++)
        val += inversions(n-1, k-j);
    return dp[n][k] = val;
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, k, i, j;
        scanf("%d%d", &n, &k);
        for (i = 1; i <= n; i++)
            for (j = 0; j <= k; j++)
                dp[i][j] = -1;
        printf("%d\n", inversions(n, k));
    }
    return 0;
}

Спустя день мне удалось решить проблему с помощью динамического программирования. Я отправил его, и мой код был принят SPOJ, так что я полагаю, что поделюсь своими знаниями здесь для всех, кто заинтересован в будущем.

Заглянув на страницу Википедии, где обсуждается инверсия в дискретной математике, я нашел интересную рекомендацию внизу страницы.

Количество перестановок n элементов с k инверсиями; Номера Махоняна: A008302

Я щелкнул ссылку на OEIS, и он показал мне бесконечную последовательность целых чисел, называемую треугольником чисел Махона.

1, 1, 1, 1, 2, 2, 1, 1, 3, 5, 6, 5, 3, 1, 1, 4, 9, 15, 20, 22, 20, 15, 9, 4, 1, 1, 5, 14, 29, 49, 71, 90, 101, 101, 90, 71, 49, 29, 14, 5, 1, 1, 6, 20, 49, 98, 169, 259, 359, 455, 531, 573, 573, 531, 455, 359, 259, 169, 98, 49, 20, 6, 1 . . .

Мне было любопытно, что это за числа, поскольку они показались мне знакомыми. Затем я понял, что видел подпоследовательности 1, 3, 5, 6, 5, 3, 1 раньше. Фактически, это был ответ на проблему для нескольких пар (n, k), а именно (4, 0), (4, 1), (4, 2), (4, 3), (4, 4) , (4, 5), (4, 6). Я посмотрел на то, что было по обе стороны от этой подпоследовательности, и был поражен, увидев, что все это действительные (т.е. более 0 перестановок) ответы для n ‹4 и n> 4.

Формула для последовательности была дана как:

коэффициенты в разложении Product_ {i = 0..n-1} (1 + x + ... + x ^ i)

Мне было достаточно легко понять и проверить это. Я мог бы взять любое n и вставить в формулу. Тогда коэффициент для члена x ^k будет ответом для (n, k).

Я покажу пример для n = 3.

(x0)(x0 + 1)(x0 + x1 + x2) = (1)(1 + x)(1 + x + x2) = (1 + x)(1 + x + x2) = 1 + x + x + x2 + x2 + x3 = 1 + 2x + 2x2 + x3

Окончательное разложение было 1 + 2x + 2x2 + x3, а коэффициенты членов x ^k были 1, 2, 2 и 1 для k = 0, 1, 2, 3 соответственно. Это просто все допустимые числа инверсий для 3-элементных перестановок.

1, 2, 2, 1 - это 3-я строка чисел Махонада, когда они расположены в таблице следующим образом:

1
1 1
1 2 2 1
1 3 5 6 5 3 1
etc.

Итак, в основном вычисление моего ответа сводилось к простому вычислению n-й махонианской строки и взятию k-го элемента с k, начиная с 0, и печати 0, если индекс был вне допустимого диапазона. Это был простой случай восходящего динамического программирования, поскольку каждую i-ю строку можно было использовать для простого вычисления i + 1-й строки.

Ниже приведено решение Python, которое я использовал, которое работало всего за 0,02 секунды. Максимальный предел времени для этой проблемы составлял 3 секунды для заданных тестовых примеров, и раньше я получал ошибку тайм-аута, поэтому я думаю, что эта оптимизация довольно хороша.

def mahonian_row(n):
    '''Generates coefficients in expansion of 
    Product_{i=0..n-1} (1+x+...+x^i)
    **Requires that n is a positive integer'''
    # Allocate space for resulting list of coefficients?
    # Initialize them all to zero?
    #max_zero_holder = [0] * int(1 + (n * 0.5) * (n - 1))

    # Current max power of x i.e. x^0, x^0 + x^1, x^0 + x^1 + x^2, etc.
    # i + 1 is current row number we are computing
    i = 1
    # Preallocate result
    # Initialize to answer for n = 1
    result = [1]
    while i < n:
        # Copy previous row of n into prev
        prev = result[:]
        # Get space to hold (i+1)st row
        result = [0] * int(1 + ((i + 1) * 0.5) * (i))
        # Initialize multiplier for this row
        m = [1] * (i + 1)
        # Multiply
        for j in range(len(m)):
            for k in range(len(prev)):
                result[k+j] += m[j] * prev[k]
        # Result now equals mahonian_row(i+1)
        # Possibly should be memoized?
        i = i + 1
    return result


def main():
    t = int(raw_input())
    for _ in xrange(t):
        n, k = (int(s) for s in raw_input().split())
        row = mahonian_row(n)
        if k < 0 or k > len(row) - 1:
            print 0
        else:
            print row[k]


if __name__ == '__main__':
    main()

Я понятия не имею о временной сложности, но абсолютно уверен, что этот код можно улучшить с помощью мемоизации, поскольку имеется 10 заданных тестовых примеров, и вычисления для предыдущих тестовых примеров могут быть использованы для «обмана» будущих тестовых примеров. Я сделаю эту оптимизацию в будущем, но, надеюсь, этот ответ в его текущем состоянии поможет любому, кто попытается решить эту проблему в будущем, поскольку он избегает наивного подхода факторной сложности к генерации и повторению всех перестановок.

Если есть решение для динамического программирования, вероятно, есть способ сделать это шаг за шагом, используя результаты для перестановок длины n, чтобы помочь с результатами для перестановок длины n + 1.

Учитывая перестановку длины n - значения 1-n, вы можете получить перестановку длины n + 1, добавив значение (n + 1) в n + 1 возможных позициях. (n + 1) больше, чем любой из 1-n, поэтому количество инверсий, которые вы создаете, когда вы это делаете, зависит от того, где вы его добавляете - добавьте его в последнюю позицию, и вы не создадите инверсий, добавьте его в предпоследнюю позиции, и вы создаете одну инверсию, и так далее - посмотрите назад на n = 4 случая с одной инверсией, чтобы проверить это.

Итак, если вы рассмотрите одно из n + 1 мест, где вы можете добавить (n + 1), если вы добавите его в место j, считая справа, так что последняя позиция как позиция 0, количество перестановок с K инверсий, которые это создает, является количеством перестановки с инверсиями Kj на n местах.

Итак, если на каждом шаге вы подсчитываете количество перестановок с K инверсиями для всех возможных K, вы можете обновить количество перестановок с K инверсиями для длины n + 1, используя количество перестановок с K инверсиями для длины n.

Мы можем использовать динамическое программирование для решения этой проблемы. у нас есть n мест, которые нужно заполнить числами от 1 до n, _ _ _ _ _ _ _ возьмите n = 7, тогда в самом первом месте мы можем достичь не более n-1 инверсии и, по крайней мере, 0, аналогично для второго места мы можем достичь не более n-2 инверсии и не менее 0, в общем, мы можем достичь не более ni инверсий по i-му индексу, независимо от выбора числа, которое мы разместили ранее. наша рекурсивная формула будет выглядеть так:

f (n, k) = f (n-1, k) + f (n-1, k-1) + f (n-1, k-2) ............. f (n-1, max (0, k- (n-1)) без инверсии одна инверсия две инверсии n-1 инверсия мы можем достичь 0 инверсий, поместив наименьшее из оставшихся чисел из набора (1, n) 1 инверсия поместив второй по величине и т. д.,

базовым условием для нашей рекурсивной формулы будет.

if (i == 0 && k == 0) return 1 (допустимая перестановка)

if (i == 0 && k! = 0) вернуть 0 (недопустимая перестановка).

если мы нарисуем дерево рекурсии, мы увидим подзадачи, повторяющиеся несколько раз. Следовательно, используйте мемоизацию, чтобы уменьшить сложность до O (n * k).

Основная проблема при вычислении этих коэффициентов - размер заказа результирующего продукта. Полиномиальное произведение i = 1,2, .., n {(1 + x). (1 + x + x ^ 2) .... (1 + x + x ^ 2 + .. + x ^ i) + ... (1 + x + x ^ 2 + ... + x ^ n) будет иметь порядок, эквивалентный n * (n + 1). Следовательно, это накладывает ограничительный вычислительный предел на процесс. Если мы используем процесс, в котором предыдущие результаты для Продукта для n-1 используются в процессе вычисления Продукта для n, мы рассматриваем хранение (n-1) * n целых чисел. Можно использовать рекурсивный процесс, который будет намного медленнее, и снова он ограничен целыми числами, меньшими, чем квадратный корень из обычного размера целого числа. Ниже приведен примерный и готовый рекурсивный код для этой проблемы. Функция mahonian (r, c) возвращает c-й коэффициент для r-го Продукта. Но опять же, это очень медленно для больших продуктов, превышающих 100 или около того. Запустив это, можно увидеть, что рекурсия явно не является ответом.

unsigned int numbertheory::mahonian(unsigned int r, unsigned int c)
  {
      unsigned int result=0;
      unsigned int k;

     if(r==0 && c==0)
       return 1;
     if( r==0 && c!=0)
      return 0;

   for(k=0; k <= r; k++)
       if(r > 0 && c >=k)
           result = result + mahonian(r-1,c-k);

   return result;

}

В качестве интереса я добавил следующее, которое представляет собой версию Sashank на C ++, которая намного быстрее, чем мой пример рекурсии. Обратите внимание, я использую библиотеку броненосцев.

uvec numbertheory::mahonian_row(uword n){
 uword i = 2;
 uvec current;
 current.ones(i);
 uword current_size;
 uvec prev;
 uword prev_size;

 if(n==0){
   current.ones(1);
   return current;
 }

 while (i <= n){                  // increment through the rows
   prev_size=current.size();     // reset prev size to current size
   prev.set_size(prev_size);     // set size of prev vector
   prev= current;                //copy contents of current to prev vector
   current_size =1+ (i*(i+1)/2);      // reset current_size
   current.zeros(current_size);    // reset current vector with zeros

   for(uword j=0;j<i+1; j++)       //increment through current vector
      for(uword k=0; k < prev_size;k++)
         current(k+j) += prev(k);
   i++;                                        //increment to next row
}
return current;                                //return current vector
 }

 uword numbertheory::mahonian_fast(uword n, uword c) {
**This function returns the coefficient of c order of row n of
**the Mahonian numbers
    // check for input errors
    if(c >= 1+ (n*(n+1)/2)) {
        cout << "Error. Invalid input parameters" << endl;
   }
   uvec mahonian;
   mahonian.zeros(1+ (n*(n+1)/2));
   mahonian = mahonian_row(n);
   return mahonian(c);
 }