algorithm - "K-transformed"排列

Question

几天来我一直在努力解决这个问题，并在网上详尽地搜索了有关如何解决它的任何提示。如果您喜欢面向数学的编程问题，请看一看!

这是 problem (PDF courtesy of UVA) :

Consider a sequence of n integers < 1 2 3 4 ... n >. Since all the values are distinct, we know that there are n factorial permutations. A permutation is called K-transformed if the absolute difference between the original position and the new position of every element is at most K. Given n and K, you have to find out the total number of K-transformed permutations.

...

Input: The first line of input is an integer T (T < 20) that indicates the number of test cases. Each case consists of a line containing two integers n and K. (1 <= n <= 10^9) and (0 <= K <= 3).

Output: For each case, output the case number first followed by the required result. Since the result could be huge, output result modulo 73405.

问题解决者，Sohel Hafiz ，将此问题归类为“Fast Matrix Exponentiation”。不幸的是，我在此处链接的谷歌搜索似乎没有显示任何相关链接，除了维基百科页面上充斥着数学术语和符号(我证明维基百科不能很好地替代任何数学教科书)。

这是我到目前为止所做的:

此代码将通过递归计算 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 显然是斐波那契数列。这里 main 中的魔术函数是我后来发现的，几乎是偶然的。它仅适用于 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。

剩下的就是找到一个非递归方程，该方程可以在合理的时间内(不到 10 秒)找到 K=3 的任何值。

编辑: 我对用于在合理时间内解决任何给定 n 和 k 问题的算法很感兴趣。我不希望任何人通过按照竞赛规则的规范编写代码来实际确认他们的算法是否有效，我在答案中寻找的是对如何处理问题和应用数值方法来获得解决方案的描述。

Answer 1

这个问题有两个部分。首先是计算出 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]。