我希望了解在给定数字集合{a1,a2,a3,...}中,将数字x表示为若干个数字之和的方法有哪些。每个数字可以重复使用。
例如,如果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。
我希望了解在给定数字集合{a1,a2,a3,...}中,将数字x表示为若干个数字之和的方法有哪些。每个数字可以重复使用。
例如,如果x=4且a1=1,a2=2,则表示x=4的方法有:
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
由于总和的顺序很重要,因此具有以下关系:
S( n, {a_1, ..., a_k} ) = sum[ S( n - a_i, {a_1, ..., a_k} ) for i in 1, ..., k ].
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 - max{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。
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.
O(log x)
,可以使用幂的平方法来计算 A^n
。A^n
的右下角元素包含所需的值 S(n)
。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;
}