Сделать сумму K с N монетами

Question

Данные N монеты номиналов A [1], A [2] ... A [n], где каждый A [i] уникален, а их бесконечные монеты каждого номинала. не более 15 видов монет, что означает N < = 15.

Теперь мы должны распределить эти монеты таким образом, что общая сумма всех распределенных монет стал К. два распределения различны, если последовательность распределения отличается, что означает, что если нам нужно сделать сумму 8, то 2,3,2 является различное распределение от 2,2,3.

Нам необходимо найти подсчет этих распределений.

Как это может быть сделано в качестве эффективного способа К может доходить до 10^18, хотя Н и А [я] оба меньше или равно 15.

Пример: Пусть K = 19 и N = 2 и наименованиями будут [4,5], тогда здесь ответ будет 4, поскольку четыре возможных способа: [5,5,5,4], [5,5,4,5], [5,4,5,5] и [4,5,5,5].

Подход 1: Я знаю о проблеме с монеткой и думаю, что она может помочь. Но не знаю, как ее изменить.

Answer 1

Позвольте C[K] быть числом способов сделать общее число K. У нас есть линейная однородная рекуррентные

C[K] | K < 0 = 0 
    | K == 0 = 1 
    | K > 0 = sum from j=1 to N of C[K - A[j]]. 

Это не повторение для обычной проблемы изменения монеты, потому что это не проблема изменения обычно монета.

Let M = max from j=1 to N of A[j]. Тогда есть матрица L такая, что для всех K,

L [C[K - 1]] = [C[K]  ] 
    [...  ] [...   ] 
    [C[K - M]] [C[K - M + 1]]. 

Для, например, A = [1, 3, 4], эта матрица L является

[1 0 1 1] 
[1 0 0 0] 
[0 1 0 0] 
[0 0 1 0]. 

Первая строка имеет те в столбцах A[j] для j=1 к N (или , если есть отличимые монеты с одинаковым значением, более высокие числа). Остальные строки имеют только под главной диагональю.

[1 0 1 1] [C[3]] = [C[3]  + C[1] + C[0]] = [C[4]] 
[1 0 0 0] [C[2]] [C[3]      ] [C[3]] 
[0 1 0 0] [C[1]] [  C[2]    ] [C[2]] 
[0 0 1 0] [C[0]] [    C[1]  ] [C[1]] 

Для того, чтобы пропустить вперед быстро в последовательности K, использовать exponentiation by squaring для вычисления L^K, затем умножить на вектор начальных условий [C[0] ... C[-M + 1]]' = [1 0 ... 0]' и возвращают первую запись (то есть, верхний левый ввод мощности матрицы).

Answer 2

Предполагает, что K является 10^18 и A = [1,2]. считая только ответы типа [1,1,.....2],[1,1,......2,1], у вас будет 10^18-1 таких массивов, которые вам нужно будет вернуть. Поэтому я пришел к выводу, что с помощью ограничений, которые вы представили, эта проблема неразрешима компьютером из-за сложности времени и пространства.