Сколько способов представить число из заданного набора чисел

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

Если вы хотите найти все возможные способы представления числа N из заданного набора чисел, вы должны следовать динамическому программному решению, как уже предлагалось.

Но если вы просто хотите узнать количество способов, то вы имеете дело с проблемой функции ограниченного разбиения .

Ограниченная функция разбиения p (n, dm) ≡ p (n, {d1, d2, ..., dm}) - это число разбиений n на натуральные числа {d1, d2,. , , , дм}, каждый не больше чем n.

Вам также следует проверить статью в Википедии о функции разделов без ограничений , где нет ограничений.

PS. Если также допустимы отрицательные числа, то, вероятно, есть (счетно) бесконечные способы представить вашу сумму.

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

PS2. Это скорее математический вопрос, чем программный

Answer 2

Вычисление количества комбинаций может быть выполнено в 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 происходит в наборе.Также S (n) = 0 для n <0.Этот вид рецидива можно сформулировать в виде матрицы <code>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;
}

Answer 3

Поскольку порядок в сумме важен, он имеет место:

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) значения, при которых диапазон будет линейно расти в 10 * *

Редактировать 2: @ Андрей сэмплов. Первый метод легко реализовать, и он работает для «small» 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 (> 10 ^ 5 в Python). Поскольку требуются только последние значения max(a_i), его можно реализовать с циклическим буфером.

Эти значения очень быстро растут, например, S (100000, [1,2,8]) составляет ~ 10 ^ 21503.