多少的方式来重新present一个数从给定的一组数字 [英] How many ways to represent a number from a given set of numbers
问题描述
我想知道有多少种方法才能重新present一个数字x从一组给定的数字数的总和{A1.A2，A3，...}。每个数字都可以多次采取更多。
I want to know in how many ways can we represent a number x as a sum of numbers from a given set of numbers {a1.a2,a3,...}. Each number can be taken more than once.
例如，如果x = 4和A1 = 1，A2 = 2，然后再presenting途径X = 4是：
For example, if x=4 and a1=1,a2=2, then the ways of representing x=4 are:
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
办法。因此数= 5。
Thus the number of ways =5.
我想知道，如果存在一个公式或其他一些快速的方法来做到这一点。我无法通过它蛮力。我想写code吧。
I want to know if there exists a formula or some other fast method to do so. I can't brute force through it. I want to write code for it.
注：x可以大到10 ^ 18。方面A1的数目，A2，A3，...可以长达15，并且每个a1的，A2，A3，...也可仅达15
Note: x can be as large as 10^18. The number of terms a1,a2,a3,… can be up to 15, and each of a1,a2,a3,… can also be only up to 15.
推荐答案
计算组合的数量可以在 0（对X）来完成，无视所花费的时间对任意大小的整数执行矩阵乘法。
Calculating the number of combinations can be done in O(log x), disregarding the time it takes to perform matrix multiplication on arbitrarily sized integers.
组合的数量可以被配制为复发。让 S（N）是如何从一组加数字进行编号 N 的数量。复发是
The number of combinations can be formulated as a recurrence. Let S(n) be the number of ways to make the number n by adding numbers from a set. The recurrence is
S(n) = a_1*S(n-1) + a_2*S(n-2) + ... + a_15*S(n-15),
其中， A_I 是时代我的数量发生在一组。另外，S（N）= 0对于n℃下。这种复发可以在尺寸15 * 15的矩阵 A 的角度来制定（或更少数量最多的是中集是小）。然后，如果你有一列向量 V 包含
where a_i is the number of times i occurs in the set. Also, S(n)=0 for n<0. This kind of recurrence can be formulated in terms of a matrix A of size 15*15 (or less is the largest number in the set is smaller). Then, if you have a column vector V containing
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 。非正式地，那些在基质中移动的列向量的一行上的元件，并且矩阵的最后一行，计算最新的术语
where a_i is as defined above. The proof that the multiplication of this matrix with a vector of S(n_14) ... S(n) works can be immediately seen by performing the multiplication manually; the last element in the vector will be equal to the right hand side of the recurrence with n+1. Informally, the ones in the matrix shifts the elements in the column vector one row up, and the last row of the matrix calculates the newest term.
为了计算任意长期 S（N）的复发是计算 A ^ N * V ，其中 V 等于
In order to calculate an arbitrary term S(n) of the recurrence is to calculate A^n * V, where V is equal to
S(-14) S(-13) ... S(-1) S(0) = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1.
为了让运行时降低到 0（对X），可以使用的幂的平方计算 A ^ N 。
In order to get the runtime down to O(log x), one can use exponentiation by squaring to calculate A^n.
在事实上，这是足以完全忽略列向量，右下角的元素 A ^ N 包含所需的值 S（N ）。
In fact, it is sufficient to ignore the column vector altogether, the lower right element of A^n contains the desired value S(n).
在的情况下在上述的解释是难以遵循，我已经提供，其计算在我上述的方式组合的数量的C程序。要注意的是它会溢出一个64位的整数非常快。你可以更进一步得到一个高precision使用 GMP 浮点类型，虽然你赢了'吨得到一个确切的答案。
In case the above explanation was hard to follow, I have provided a C program that calculates the number of combinations in the way I described above. Beware that it will overflow a 64-bits integer very quickly. You'll be able to get much further with a high-precision floating point type using GMP, though you won't get an exact answer.
不幸的是，我看不到一个快速的方法来获得数字一个确切的答案，在 X = 10 ^ 18 ，因为答案可能远远大于<如code> 10 ^ X 。
Unfortunately, I can't see a fast way to get an exact answer for numbers such at x=10^18, since the answer can be much larger than 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;
}
这篇关于多少的方式来重新present一个数从给定的一组数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
