几天来，我一直在抨击这个问题，并在网上搜索有关如何解决问题的任何提示。如果您喜欢以数学为导向的编程问题，请查看！
这里是 问题（PDF由UVA提供）：
考虑n个整数的序列<1 2 3 4 ... n>。由于所有值都是不同的，我们知道有n个阶乘排列。如果每个元素的原始位置和新位置之间的绝对差值最多为K，则置换被称为K变换。给定n和K，您必须找出K变换的排列的总数。
...
输入：
第一行输入是整数T（T <20），表示测试用例的数量。每个情况由包含两个整数n和K的行组成（1 <= n <= 10 ^ 9）和（0 <= K <= 3）。
输出：
对于每种情况，首先输出案例编号，然后输出所需的结果。由于结果可能很大，输出结果模73405。
问题制定者， 索赫哈菲兹，将此问题归类为“快速矩阵指数“不幸的是，我在这里链接的谷歌搜索似乎没有显示任何相关的链接，除了维基百科页面厚厚的数学术语和符号（维基百科已证明我是任何数学教科书的不良替代品）。
这是我到目前为止所做的：
此代码将通过递归计算低值n和k的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显然是Fibonacci序列。
主要的神奇功能是我后来想到的，几乎是偶然的。它仅适用于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。
剩下的就是找到一个非递归方程，可以在合理的时间内（10s以下）找到K = 3的任何值。
编辑： 我对用于在合理的时间内解决任何给定n和k的问题的算法感兴趣。我不希望任何人通过将代码写入竞赛规则的规范来确实证实他们的算法是有效的，我在答案中寻找的是如何解决问题并应用数值方法来达成解决方案的描述。
以来 ķ 它很低，它自然落在矩阵求幂上。
每个项目最多可以结束 ķ 位置从它的起始位置。这最多给出（2 ķ - 1）职位，但有些职位已经被占用。你可以有2个2 ķ - 1 可能的配置（最接近的（2 ķ -1）插入物品时。任何未占用位置的每个新项目都会生成一个新配置，一个新的，一个新的......
您需要弄清楚从每个配置到其他配置可以获得多少种方法。你可以使用蛮力，并保存值。如果您知道这一点，可以将数字放在矩阵中;每列都是from-configuration，每一行都是to-configuration。
考虑计数向量 v;其中的每个单元格代表了进入某些配置的方式 ñ 脚步。从初始计数向量开始（全部为零，除了表示空配置的1之外， ñ = 0）。如果将此向量与矩阵相乘（v X 一个），你将这些计数提前一步（ñ = 1）。重复其他步骤。
现在是有趣的部分。如果将此矩阵与其自身相乘（一个 X 一个），你将得到一个提前两代移动的矩阵。再次（一个2 X 一个2）你会得到一个移动4代的矩阵。您可以使用此技术在几次迭代中将其移动数千（或数百万）代。
你可以阅读更多关于 通过平方取幂 在维基百科上。
如果上述速度太慢，您可以尝试为找到的值找到递归关系。取序列的前几个值，并将它们放在方程系统中：
一个 · X1 + b · X2 = X3
一个 · X2 + b · X3 = X4
解决 一个 和 b。然后生成序列，将最后两个数字乘以 一个 和 b 并添加以获得下一个。
如果这不重现序列，您可以增加大小：
一个 · X1 + b · X2 + C · X3 = X4
一个 · X2 + b · X3 + C · X4 = X五
一个 · X3 + b · X4 + C · X五 = X6
解决 一个， b 和 C。进一步增加，直到你得到有效的东西。如果你再迈出一步，你应该得到一个不太确定的系统。
可能会发生没有递归关系（至少没有线性关系）。在这种情况下，你可以增加大小，但你永远不会找到任何有用的东西。
举一个简单的例子。我们考虑一下 ķ 这将给我们一个大小为3的邻域（= 2 ķ + 1），和8种不同的配置（= 22 ķ + 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·一个 = 2
这将解决 一个 = 2.但是如果我们尝试下一个值，我们将看到如果已经在下一个值上失败了：
2·一个 = 2·2 = 4≠3。
接下来，让我们尝试一个大小为2的系统：
1·一个 + 2·b = 3
2·一个 + 3·b = 5
这解决了 一个 = b 这将实际产生整个序列。
3·一个 + 5·b = 3·1 + 5·1 = 8
5·一个 + 8·b = 5·1 + 8·1 = 13
...
如果我们尝试更大的系统，我们将遇到问题：
1·一个 + 2·b + 3·C = 5
2·一个 + 3·b + 5·C = 8
3·一个 + 5·b + 8·C = 13
这解决了 一个 = 1 - C， b = 2 - C，没有任何价值 C。
如果我们尝试序列 ķ = 2（用上述方法生成）：1 2 6 14 31 73 172 400 932 2177
直到大小5，这将无法提供有效的解决方案： 一个 = -1， b = 0， C = 2， d = 0， Ë = 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]。