我希望了解在给定数字集合{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。
从给定的数集中表示一个数字有多少种方法？
5
因此，方法总数=5。
我想知道是否存在公式或其他快速方法来解决这个问题。 我不能通过暴力来解决它。 我想为此编写代码。
注：x可以达到10^18。 a1，a2，a3，...的项数最多可达15个，并且每个a1，a2，a3，...也只能达到15。
- Andrew
8
由于您想要识别为“不同”的方式，这很困难。如果F(4)是3或32，那将会容易得多。 - harold
1这个问题与编程无关，更适合在数学 StackExchange 上讨论。 - chrislgarry
类似于：https://dev59.com/FUnSa4cB1Zd3GeqPOX2S - Lior Kogan
1如果集合中的数字是受某个值限制的整数，那么可以使用动态规划。 - Anonym Mus
@stubbscroll 是的，我在问题中已经说明了a1、a2、a3等项的数量不超过15个，每个项的值也在1到15之间。您能否详细解释一下如何应用DP呢？因为我对它有很大的疑虑。 - Andrew
显示剩余3条评论
3个回答
4
由于总和的顺序很重要，因此具有以下关系：
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 - 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。
- Ante
5
我无法承受线性复杂度，因为n可能高达10^18，而且我需要我的代码在几秒钟内运行。不管怎样，谢谢。 - Andrew
我感到困惑，因为这本应该是一个简单的问题。以下是其中一个样例测试案例：
输入：x=13，集合为{1,2,8}。输出=415。 - Andrew
另一个样例测试案例：
输入：x=15，集合为{1,2,3,4,5}。输出=13624。 - Andrew
@Ante。我不需要担心输出增长得太快，因为我必须将输出取模一个大质数，即1000000007。 - Andrew
我需要一个方法，在一秒钟左右就可以输出x=10^18并设置{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}。我知道这肯定是可解的。 - Andrew
3
- pnezis
1
你能给出一些具体的公式，并提供一些计算上的见解吗？我需要编写代码。顺便说一句，注意顺序很重要，因此一个分区函数可能不够用。还有，是的，这些数字不能为负数。 - Andrew
3
计算组合数可以在O(log x)时间内完成，不考虑对任意大小的整数执行矩阵乘法所需的时间。
组合数可以表示为一个递归式。设S(n)是从集合中添加数字得到数字n的方法数。递归式为：
为了把运行时间降到
事实上，完全可以忽略列向量，
如果以上解释难以理解，我提供了一个 C 程序，按照我上面描述的方式计算组合数。请注意，它很快就会溢出 64 位整数。您可以使用GMP高精度浮点类型来大大扩展范围，尽管您将无法获得准确答案。
不幸的是，我看不到在类似
组合数可以表示为一个递归式。设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.
为了把运行时间降到
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;
}
- Anonym Mus
1
非常好 :-) 清晰的方法和易于实现。 - Ante
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接