有多少种方法来表示给定数字集中的一个数字

Question

我想知道我们可以用多少种方式将数字 x 表示为给定数字集合 {a1.a2,a3,...} 中的数字之和。每个数字可以被多次取走。

\n\n

例如，如果x=4且a1=1,a2=2，则x=4的表示方式为：

\n\n

1+1+1+1\n1+1+2\n1+2+1\n2+1+1\n2+2\n

\n\n

因此路数=5。

\n\n

我想知道是否存在一个公式或其他一些快速方法可以做到这一点。我无法用暴力破解它。我想为它编写代码。

\n\n

注意：x 可以大到 10^18。a1,a2,a3,\xe2\x80\xa6 的项数最多可达 15 个，并且 a1,a2,a3,\xe2\x80\xa6 中的每一项也最多只能达到 15 个。

\n

Answer 1

计算组合的数量可以在 中完成O(log x)，而不考虑对任意大小的整数执行矩阵乘法所需的时间。

组合的数量可以表示为递归。让为通过将一组数字相加来S(n)得出该数字的方法数。n复发率是

S(n) = a_1*S(n-1) + a_2*S(n-2) + ... + a_15*S(n-15),

其中是集合中出现的a_i次数。i另外，当 n<0 时，S(n)=0。这种递归可以用A大小为 15*15 的矩阵来表示（或更小是集合中最大的数更小）。然后，如果您有一个V包含的列向量

S(n-14) S(n-13) ... S(n-1) S(n),

那么矩阵乘法的结果A*V将是

S(n-13) S(n-12) ... S(n) S(n+1).

矩阵A定义如下：

0    1    0    0    0    0    0    0    0    0    0    0    0    0    0
0    0    1    0    0    0    0    0    0    0    0    0    0    0    0
0    0    0    1    0    0    0    0    0    0    0    0    0    0    0
0    0    0    0    1    0    0    0    0    0    0    0    0    0    0
0    0    0    0    0    1    0    0    0    0    0    0    0    0    0
0    0    0    0    0    0    1    0    0    0    0    0    0    0    0
0    0    0    0    0    0    0    1    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0    1    0    0    0    0    0    0
0    0    0    0    0    0    0    0    0    1    0    0    0    0    0
0    0    0    0    0    0    0    0    0    0    1    0    0    0    0
0    0    0    0    0    0    0    0    0    0    0    1    0    0    0
0    0    0    0    0    0    0    0    0    0    0    0    1    0    0
0    0    0    0    0    0    0    0    0    0    0    0    0    1    0
0    0    0    0    0    0    0    0    0    0    0    0    0    0    1
a_15 a_14 a_13 a_12 a_11 a_10 a_9  a_8  a_7  a_6  a_5  a_4  a_3  a_2  a_1 

其中a_i是如上面所定义的。S(n_14) ... S(n)通过手动执行乘法，可以立即看到该矩阵与工作向量相乘的证明；向量中的最后一个元素将等于 的递归式的右侧n+1。通俗地说，矩阵中的元素将列向量中的元素向上移动一行，矩阵的最后一行计算最新项。

为了计算S(n)递推的任意项，需要计算A^n * V，其中V等于

S(-14) S(-13) ... S(-1) S(0) = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1.

为了将运行时间降低到O(log x)，可以使用乘方乘方来计算A^n。

事实上，完全忽略列向量就足够了， 的右下元素A^n包含所需的值S(n)。

如果上面的解释很难理解，我提供了一个 C 程序，它可以按照我上面描述的方式计算组合的数量。请注意，它很快就会溢出 64 位整数。尽管您不会得到确切的答案，但使用GMP可以获得高精度浮点类型，从而获得更进一步的结果。

不幸的是，我看不到一种快速方法来获得 等数字的精确答案x=10^18，因为答案可能比 更大10^x。

#include <stdio.h>
typedef unsigned long long ull;

/*  highest number in set */
#define N 15

/*  perform the matrix multiplication out=a*b */
void matrixmul(ull out[N][N],ull a[N][N],ull b[N][N]) {
  ull temp[N][N];
  int i,j,k;
  for(i=0;i<N;i++) for(j=0;j<N;j++) temp[i][j]=0;
  for(k=0;k<N;k++) for(i=0;i<N;i++) for(j=0;j<N;j++)
    temp[i][j]+=a[i][k]*b[k][j];
  for(i=0;i<N;i++) for(j=0;j<N;j++) out[i][j]=temp[i][j];
}

/*  take the in matrix to the pow-th power, return to out */
void matrixpow(ull out[N][N],ull in[N][N],ull pow) {
  ull sq[N][N],temp[N][N];
  int i,j;
  for(i=0;i<N;i++) for(j=0;j<N;j++) temp[i][j]=i==j;
  for(i=0;i<N;i++) for(j=0;j<N;j++) sq[i][j]=in[i][j];
  while(pow>0) {
    if(pow&1) matrixmul(temp,temp,sq);
    matrixmul(sq,sq,sq);
    pow>>=1;
  }
  for(i=0;i<N;i++) for(j=0;j<N;j++) out[i][j]=temp[i][j];
}

void solve(ull n,int *a) {
  ull m[N][N];
  int i,j;
  for(i=0;i<N;i++) for(j=0;j<N;j++) m[i][j]=0;
  /*  create matrix from a[] array above */
  for(i=2;i<=N;i++) m[i-2][i-1]=1;
  for(i=1;i<=N;i++) m[N-1][N-i]=a[i-1];
  matrixpow(m,m,n);
  printf("S(%llu): %llu\n",n,m[N-1][N-1]);
}

int main() {
  int a[]={1,1,0,0,0,0,0,1,0,0,0,0,0,0,0};
  int b[]={1,1,1,1,1,0,0,0,0,0,0,0,0,0,0};
  solve(13,a);
  solve(80,a);
  solve(15,b);
  solve(66,b);
  return 0;
}