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

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

Вот проблема (PDF-файл предоставлен UVA) :

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

. ..

Ввод: Первая строка ввода - это целое число T (T

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

Создатель задачи, Соэль Хафиз , отнесла эту проблему к категории « Быстрое матричное возведение в степень ». К сожалению, поиск в Google, на который я ссылался, похоже, не вызывает никаких релевантных ссылок, кроме страницы Википедии, наполненной математическим жаргоном и обозначениями (Википедия оказалась плохой заменой любому учебнику математики).

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

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

#include 
#include 
#include 
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;j0)
    low = x-k;
  if (x+k+1

Первое, что я понял, это то, что 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 секунд).

РЕДАКТИРОВАТЬ: Меня интересует алгоритм, используемый для решения проблемы для любых заданных n и k в разумные сроки. Я не ожидаю, что кто-то действительно подтвердит, что их алгоритм работает, написав код в соответствии со спецификациями правил конкурса. В ответ я ищу описание того, как подойти к проблеме и применить численные методы для достижения решения.