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

Question

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

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

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2

因此方式的数量=5。

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

注意：x 可以大到 10^18。 a1,a2,a3,… 项的数量最多可以为 15，并且 a1,a2,a3,… 中的每一项也最多只能为 15。

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。这种递归可以用大小为 15*15 的矩阵 A 来表示（或更小是集合中最大的数更小）。然后，如果您有一个列向量 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.

In为了将运行时间降低到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;
}

Answer 2

由于总和的顺序很重要，因此它成立：

S( n, {a_1, ..., a_k} ) = sum[ S( n - a_i, {a_1, ..., a_k} ) for i in 1, ..., k ].

这对于动态规划解决方案来说已经足够了。如果值 S(i, set) 从 0 到 n 创建，则复杂度为 O( n*k ) 。

编辑：只是一个想法。将一个求和视为一个序列 (s_1, s_2, ..., s_m)。序列第一部分的总和在某个时刻将大于n/2，令其对于索引j：

s_1 + s_2 + ... + s_{j-1} < n / 2,
s_1 + s_2 + ... + s_j = S >= n / 2.

最多有k不同的和S，并且对于每个S，最多有k个可能的最后元素s_j。所有可能性 (S,s_j) 将序列总和分为 3 部分。

s_1 + s_2 + ... + s_{j-1} = L,
s_j,
s_{j+1} + ... + s_m = R.

它保持n/2 >= L, R > n/2 - 最大值{a_i}。这样，上面的公式就有了更复杂的形式：

S( n, set ) = sum[ S( n-L-s_j, set )*S( R, set ) for all combinations of (S,s_j) ].

我不确定，但我认为每一步都需要“创建”范围
S(x,set) 值，其中范围将按因子 max{a_i} 线性增长。

编辑 2：@Andrew 示例。第一种方法很容易实现，并且适用于“小”x。这是 python 代码：

def S( x, ai_s ):
  s = [0] * (x+1)
  s[0] = 1
  for i in xrange(1,x+1):
    s[i] = sum( s[i-ai] if i-ai >= 0 else 0 for ai in ai_s )
  return s[x]

S( 13, [1,2,8] )
S( 15, [1,2,3,4,5] )

此实现存在大 x 内存问题（在 python 中>10^5）。由于只需要最后的 max(a_i) 值，因此可以使用循环缓冲区来实现它。

这些值增长得非常快，例如 S(100000, [1,2,8] ) 约为 10^21503。

Answer 3

如果您想从给定的一组数字中找到表示数字 N 的所有可能方法，那么您应该遵循已经提出的动态规划解决方案。

但如果您只想知道方法的数量，那么您正在处理受限分区函数问题。

受限配分函数 p(n, dm) ≡ p(n, {d1, d2, . . . ,
dm}) 是将 n 划分为正整数 {d1, d2,... 的次数。
。 。 , dm}，每个不大于n。

您还应该查看关于没有限制的分区函数的维基百科文章，其中没有限制申请。

附言。如果也允许负数，那么可能有（可数）无限种方式来表示您的总和。

1+1+1+1-1+1
1+1+1+1-1+1-1+1
etc...

PS2。这更像是一道数学问题，而不是编程问题