"K-преобразованные" перестановки

Я несколько дней стучал головой об этой проблеме и тщательно изучал онлайн, чтобы узнать, как ее решить. Если вам нравятся математически ориентированные проблемы программирования, пожалуйста, посмотрите!

Вот проблема (PDF любезно предоставлена ​​UVA):

Рассмотрим последовательность из n целых чисел < 1 2 3 4... n > . Поскольку все значения различны, мы знаем, что существует n факториальных перестановок. Перестановка называется K-преобразованной, если абсолютная разница между исходной позицией и новой позицией каждого элемента не более K. Учитывая n и K, вам нужно выяснить общее количество K-преобразованных перестановок.

...

Input:  Первая строка ввода представляет собой целое число T (T < 20), которое указывает количество тестовых примеров. Каждый случай состоит из строки, содержащей два целых числа n и K. (1 <= n <= 10 ^ 9) и (0 <= K <= 3).

Вывод: Для каждого случая сначала выводите номер дела, а затем требуемый результат. Поскольку результат может быть огромным, выведите результат по модулю 73405.

Задатчик, Sohel Hafiz, классифицировал эту проблему как " Fast Матричная трансформация. " К сожалению, поиск Google, который я здесь связал, похоже, не приводит к появлению каких-либо релевантных ссылок, кроме страницы Википедии, толстой с математическим жаргоном и обозначениями (Википедия доказала, что я была плохой заменой для любого математического учебника).

Вот что я сделал до сих пор:

Этот код будет вычислять путем рекурсии число K-преобразованных перестановок при малых значениях n и k, но слишком сложно. Это достаточно хорошо, чтобы создать таблицу для поиска шаблонов:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int permute(int * a, int size, int i, int k)
{
  int j;
  int total = 0;
  int x = size-i;
  int low=0;
  int high=size;
  if (i == 0)
  {
/*    for (j=0;j<size;j++)
      printf("%d, ", a[j]);
    printf("\n");
*/    return 1;
  }
  if (x-k>0)
    low = x-k;
  if (x+k+1<size)
    high = x+k+1;
  for (j=low;j<high;j++)
  {
    int b[size];
    memcpy(b,a,size*sizeof(int));
    if (b[j] == 0)
    {
      b[j] = x+1;
      total += permute(b,size,i-1,k);
    }
  }
  return total;
}

int main() 
{
  int n, k, j, y, z;
  int * arr;
  /*scanf("%d %d", &n,&k);*/ k=2;
  for (n=0;n<14;n++)
  {
    int empty[n];
    for (j=0;j<n;j++)
      empty[j] = 0;
    arr = empty;  
    z = permute(arr, n, n, k);
    y = magic(n,k);
    printf("%d %d\n",z, y);
  }
  return 0;
}

Первое, что я выяснил, заключалось в том, что k = 1, очевидно, является последовательностью Фибоначчи. Волшебная функция в главном здесь - это то, что я выяснил позже, почти случайно. Он работает ТОЛЬКО при k = 2, но точно до n = 14.

int magic(int n, int k)
{
  if (n<0)
    return 0;
  if (n==0)
    return 1;
  if (n==1)
    return 1;
  return 2*magic(n-1,k) + 2*magic(n-3,k) - magic(n-5,k);  
}

Очень странно! Я не знаю значения этой функции, но ее можно упростить для запуска в цикле, чтобы работать достаточно быстро, чтобы закончить K = 2 для значений до 10 ^ 9.

Все остальное - найти нерекурсивное уравнение, которое может найти любое значение для K = 3 за разумный промежуток времени (менее 10 секунд).

EDIT: Меня интересует алгоритм, используемый для решения проблемы для любых заданных n и k в течение разумного промежутка времени. Я не ожидаю, что кто-нибудь действительно подтвердит, что их алгоритм работает, написав код спецификации технических правил конкурса, то, что я ищу в ответе, - это описание того, как подойти к проблеме и применить численные методы для решения.

Ответы

Ответ 1

Так как K низкое, оно естественно падает на экспоненцию матрицы.

Каждый элемент может содержать не более K позиций из его стартовой позиции. Это дает не более (2 К - 1) позиции, но некоторые позиции уже могут быть заняты. При размещении элемента вы можете иметь 2 2 K - 1 возможных конфигураций (ближайшего (2 K -1) слота). Каждый новый элемент в любой незанятой позиции создаст новую конфигурацию, а новый и новый...

Вам нужно выяснить, сколько способов вы можете получить от каждой конфигурации друг к другу. Вы можете использовать грубую силу для этого и сохранить значения. Когда вы это знаете, вы можете поместить числа в матрицу; Каждый столбец является конфигурацией, и каждая строка является конфигурацией.

Рассмотрим вектор счета v; Каждая ячейка в нем представляет собой количество способов перехода к некоторой конфигурации с помощью n шагов. Начните с начального вектора-count (все нули, кроме одного 1, представляющего пустую конфигурацию, n = 0). Если вы умножаете этот вектор на матрицу (v x A), вы перемещаете эти счета вперед на один шаг (n = 1). Повторите шаги для дополнительных шагов.

Теперь идет интересная часть. Если вы умножите эту матрицу на себя (A x A), вы получите матрицу для перемещения вперед двух поколений. Опять же (A 2 x A 2), и вы получите матрицу для перемещения 4 поколений. Вы можете использовать эту технику, чтобы продвинуть ее несколько тысяч (или миллионов) поколений вперед, всего за несколько итераций.

Подробнее о возвышении по квадрату в Википедии.

Если вышеуказанное слишком медленно, вы можете попытаться найти отношение повторения для найденных значений. Возьмите первые несколько значений последовательности и поместите их в систему уравнений:

a & middot; x 1 + b & middot; x 2= x 3
a & middot; x 2 + b & middot; x 3= x 4

Решите для a и b. Затем, чтобы сгенерировать последовательность, вы умножаете последние два числа на a и b и добавляете для получения следующего.

Если это не воспроизводит последовательность, вы можете увеличить размер:

a & middot; x 1 + b & middot; x 2 + c & middot; x 3= x 4
a & middot; x 2 + b & middot; x 3 + c & middot; x 4= x 5
a & middot; x 3 + b & middot; x 4 + c & middot; x 5= x 6

Решите для a, b и c. Увеличивайте все дальше, пока не получите что-то, что работает. Если вы пройдете еще один шаг, вы должны получить недостаточно определенную систему.

Может случиться так, что нет рекуррентного отношения (по крайней мере, линейного). В этом случае вы можете увеличить размер, но вы никогда не найдете ничего, что сработает.

Сделать простой пример. Рассмотрим K = 1. Это даст нам окрестность размера 3 (= 2 K + 1) и 8 различных конфигураций (= 2 2 K + 1).

Чтобы выбрать нотацию, я буду использовать # для занятых или недоступных и . бесплатно.

Чтобы сгенерировать матрицу, мы должны рассмотреть, какие шаблоны можно преобразовать, добавив один символ.

  • Для шаблонов, начинающихся со свободного слота, мы должны поместить следующий символ в крайнее левое. В противном случае у нас будет пробел в последовательности.

  • Для шаблона ### у нас нет свободных мест для размещения чего-либо, так что это тупик.

  • Для оставшихся шаблонов может помещать символ в любое свободное место, а затем перемещать шаблон на одно место (перемещение в следующую позицию).

Матрица может выглядеть так:

    ... ..# .#. .## #.. #.# ##. ###
...  1   0   0   0   0   0   0   0
..#  0   0   1   0   0   0   0   0
.#.  0   0   0   0   1   0   0   0
.##  0   0   0   0   0   0   1   0
#..  0   0   1   0   1   0   0   0
#.#  0   0   0   0   0   0   1   0
##.  0   0   0   0   0   0   1   0
###  0   0   0   0   0   0   0   0

В качестве исходного шаблона мы возьмем #... Это связано с тем, что мы не можем поместить первый символ перед началом последовательности. Последовательность одного символа может быть записана только одним способом, поэтому начальный отсчет-вектор становится 0 0 0 0 1 0 0 0.

Последний шаблон, который мы хотим, - #... Никакой символ за пределами последовательности, но остальные должны быть заполнены. Шаблон заключается в том, что после смены. Это означает, что мы хотим посмотреть позицию 5 в векторе (считая от 1).

Первые несколько значений, которые мы получаем, следующие:

n   p(n,1)
1        1
2        2
3        3
4        5
5        8
6       13
7       21
8       34

Конечно, большая часть матрицы избыточна. Вы можете потратить некоторое время, чтобы устранить строки и столбцы. Я не буду это демонстрировать.

Как только у нас есть несколько значений, мы можем попытаться найти рекуррентное соотношение. Сначала попробуем систему размером 1:

1 & middot; a = 2

Это решит a = 2. Но если мы попробуем следующее значение, мы увидим, что если сбой уже на следующем значении:

2 & middot; a = 2 & middot; 2 = 4 & ne; 3.

Далее, попробуем систему размером 2:

1 & middot; a + 2 & middot; b = 3
2 & middot; a + 3 & middot; b = 5

Это решает к a = b = 1. Это будет фактически генерировать целую последовательность.

3 & middot; a + 5 & middot; b = 3 & middot; 1 + 5 & middot; 1 = 8
5 & ​​middot; a + 8 & middot; b = 5 & middot; 1 + 8 и middot; 1 = 13
...

Если мы попробуем еще большую систему, мы столкнемся с проблемами:

1 & middot; a + 2 & middot; b + 3 & middot; c = 5
2 & middot; a + 3 & middot; b + 5 & middot; c = 8
3 & middot; a + 5 & middot; b + 8 & middot; c = 13

Это решает к a = 1 - c, b = 2 - c, без какого-либо значения для c.

Если мы попробуем последовательность для K = 2 (сгенерированную с помощью вышеуказанного метода): 1 2 6 14 31 73 172 400 932 2177

Это не даст правильного решения до размера 5: a = -1, b = 0, c = 2, d = 0, e = 2. Это то же самое отношение, что и вы.

Ответ 2

Есть две части проблемы. Сначала рассмотрим формулу повторения для k=0, 1, 2, 3. Вторая часть вычисляет значения для больших n с использованием формулы повторения.

В первой части:

Пусть p(n, k) - число перестановок элементов n, которые k -трансформированы. Когда k=0 рекуррентность просто p(n, 0) = 1.

Для k=1 сначала рассмотрим, где 1 находится в перестановке. Он либо находится в положении 1, либо в позиции 2. Если он находится в позиции 1, остальные элементы являются исходной проблемой с элементами n-1. Итак, мы имеем p(n, 1) = p(n-1, 1) + .... Если первый элемент находится в позиции 2, то что? В этом случае второй элемент должен перейти в положение 1. На этом этапе у вас есть исходная проблема с элементами n-2. Таким образом, рекуррентность p(n, 1) = p(n-1, 1) + p(n-2, 1), которая является последовательностью Фибоначчи.

Для k=2 и k=3 вы получаете больше возможностей, но рассуждения одинаковы. [все еще разрабатывает точные повторения]

Вторая часть вычисляет решение для повторений при больших значениях n. Для этого вы помещаете рекуррент в матричную форму и выполняете повторное возведение/умножение для получения высоких степеней матрицы. Для случая k=1 матрица:

A = [0 1]
    [1 1]

Чтобы получить p(n + 2, 1), вам нужно вычислить A^n * [1, 1].