Я несколько дней стучал головой об этой проблеме и тщательно изучал онлайн, чтобы узнать, как ее решить. Если вам нравятся математически ориентированные проблемы программирования, пожалуйста, посмотрите!
Вот проблема (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 в течение разумного промежутка времени. Я не ожидаю, что кто-нибудь действительно подтвердит, что их алгоритм работает, написав код спецификации технических правил конкурса, то, что я ищу в ответе, - это описание того, как подойти к проблеме и применить численные методы для решения.
