Обновление для реальной проблемы:
Актуальная проблема намного проще.Тем не менее, трудно быть полезным без полной порчи.
Разбирая это до самого необходимого, проблема в
Учитывая k различных положительных целых чисел L1 , ..., Lk и неотрицательное целое число n , сколько различных конечных последовательностей ( a1 , ..., ar ) существуют ли такие, что 1. для всех i (1 <= <em>i <= <em>r ), ai является одним из Lj и 2. a1 + ... + ar = n .(Другими словами, количество композиций из n с использованием только данных Lj .)
Для удобства вытакже сказал, что все Lj <= 15 (и, следовательно, <em>k <= 15) и <em>n <= 10 ^ 18.И чтобы все вычисления можно было выполнить с использованием 64-разрядных целых чисел (число последовательностей растет экспоненциально с <em>n , у вас не было бы достаточно памяти для хранения точного числа для больших n), вам нужно только вычислить остаток от числа последовательностей по модулю 1000000007.
Чтобы решить такую проблему, начните с рассмотрения простейших случаев.Самые простые случаи, когда дается только один L , тогда, очевидно, существует одна допустимая последовательность, если n кратна L , и нет допустимой последовательности, если n мод L ! = 0. Это пока не помогает.Итак, рассмотрим следующие простейшие случаи: два значения L .Предположим, что это 1 и 2.
- 0 имеет одну композицию, пустая последовательность: N (0) = 1
- 1 имеет одну композицию, (1): N (1)= 1
- 2 имеет две композиции (1,1);(2): N (2) = 2
- 3 имеет три состава: (1,1,1); (1,2); (2,1): N (3) = 3
- 4 состоит из пяти композиций: (1,1,1,1); (1,1,2); (1,2,1); (2,1,1); (2,2): N (4) = 5
- 5 имеет восемь композиций, (1,1,1,1,1); (1,1,1,2); (1,1,2,1); (1,2,1,1); (2,1,1,1); (1,2,2); (2,1,2); (2,2,1): N (5) = 8
Вы можете увидеть это сейчас или вам понадобится еще несколько терминов, но вы заметите, что вы получаете последовательность Фибоначчи (смещенную на единицу), N ( n ) = F ( n + 1), следовательно, последовательность N ( n ) удовлетворяет рекуррентному отношению N ( n ) = N ( n -1) + N ( n -2) (для n > = 2; мы еще не доказали, что пока это гипотеза, основанная на определении шаблона),Теперь мы можем увидеть это, не вычисляя много значений?Конечно, есть два типа допустимых последовательностей, заканчивающиеся на 1 и заканчивающиеся на 2. Поскольку такое разбиение допустимых последовательностей ограничивает только последний элемент, число объявлений.сл.сумма до n и заканчивающаяся 1 равна N ( n -1) и номеру объявления.сл.сумма до n и заканчивающаяся на 2 равен N ( n -2).
Это рассуждение немедленно обобщается, учитывая L1 <<em>L2 <... <<em> Lk , для всех n > = Lk , у нас есть
N ( n ) = N ( n-L1 ) + N ( n-L2 ) + ... + N ( n-Lk )
с очевидной интерпретацией, если нас интересует только N ( n )% m .
Умм, эта линейная повторяемостьвсе еще оставляет вычисление N ( n ) как задачу O ( n )?
Да, но исследование нескольких из упомянутых ключевых слов быстро приводит к алгоритму, требующему только O (log n ) steps;)
Алгоритм для неверно истолкованной проблемы, более не актуален, но все еще может быть интересен:
Вопрос выглядит немного странно, поэтому я не буду приводить полный алгоритм (по крайней мере, не раньше, чем немного погуглю, чтобы проверить, является ли это конкурсным вопросом). Я надеюсь, что никакое ограничение не было опущено в описании, например, что перестановки таких представлений должны вносить только одно в подсчет, что значительно усложнит вопрос. Поэтому я считаю 1*3 + 2*4 = 11 и 2*4 + 1*3 = 11 двумя различными решениями.
Сначала несколько обозначений. Для m-кортежей чисел пусть < | > обозначает каноническое билинейное спаривание, т.е.
<a|x> = a_1*x_1 + ... + a_m*x_m. Для положительного целого числа B пусть A_B = {1, 2, ..., B} будет набором натуральных чисел, не превышающих B. Пусть N обозначает набор натуральных чисел, то есть неотрицательных целых чисел.
Для 0 <= m, k и B > 0 пусть C(B,m,k) = card { (a,x) \in A_B^m × N^m : <a|x> = k }.
Тогда ваша проблема - найти \sum_{m = 1}^15 C(15,m,k) (по модулю 1000000007).
Для полноты отметим, что C(B,0,k) = if k == 0 then 1 else 0, что может быть полезно в теоретических соображениях. Для случая положительного числа слагаемых легко найти формулу рекурсии
C(B,m+1,k) = \sum_{j = 0}^k C(B,1,j) * C(B,m,k-j)
По индукции C(B,m,_) - это свертка из m факторов C(B,1,_). Вычисление свертки двух известных функций до k равно O(k^2), поэтому, если известно C(B,1,_), это дает алгоритм O(n*k^2) для вычисления C(B,m,k), 1 <= m <= n. Ладно для малых k, но наша галактика не доживет до того, что вы вычислите C(15,15,10^18) таким образом Итак, мы можем сделать лучше? Что ж, если вы знакомы с преобразованием Лапласа, вы будете знать, что аналогичное преобразование преобразует продукт свертки в точечный продукт, который гораздо проще вычислить. Однако, хотя преобразование в этом случае легко вычислить, обратное - нет. Любая другая идея? Почему, да, давайте подробнее рассмотрим C(B,1,_).
C(B,1,k) = card { a \in A_B : (k/a) is an integer }
Другими словами, C(B,1,k) - это число делителей k, не превышающее B. Обозначим это через d_B(k). Сразу видно, что 1 <= d_B(k) <= B. Для B = 2, очевидно d_2(k) = 1 if k is odd, 2 if k is even. d_3(k) = 3 тогда и только тогда, когда k делится на 2 и на 3, следовательно, если k кратно 6, d_3(k) = 2 тогда и только тогда, когда одно из 2, 3 делит k, но не другое, то есть, если k % 6 \in {2,3,4} и, наконец, d_3(k) = 1, если ни 2, ни 3 не делит k, то есть, если gcd(k,6) = 1, тогда k % 6 \in {1,5}. Итак, мы видели, что d_2 является периодическим с периодом 2, d_3 является периодическим с периодом 6. Как правило, подобные рассуждения показывают, что d_B является периодическим для всех B, а минимальный положительный период делит B!.
При любом положительном периоде P, равном C(B,1,_) = d_B, мы можем разделить сумму в свертке (k = q * P + r, 0 <= r <P): </p>
C(B,m+1, q*P+r) = \sum_{c = 0}^{q-1} (\sum_{j = 0}^{P-1} d_B(j)*C(B,m,(q-c)*P + (r-j)))
+ \sum_{j = 0}^r d_B(j)*C(B,m,r-j)
Функции C(B,m,_) больше не являются периодическими для m >= 2, но есть простые формулы для получения C(B,m,q*P+r) из C(B,m,r). Таким образом, с C(B,1,_) = d_B и C(B,m,_), известными до P, вычисление C(B,m+1,_) до P является задачей O(P^2), получение данных, необходимых для вычисления C(B,m+1,k) для произвольно большого k, требует m таких сверток, следовательно, это O(m*P^2).
Тогда нахождение C(B,m,k) для 1 <= m <= n и произвольно большого k будет O(n^2*P^2) во времени и O(n^2*P) в пространстве.
Для B = 15 у нас есть 15! = 1.307674368 * 10 ^ 12, поэтому использовать его для P невозможно. К счастью, наименьший положительный период d_15 на намного меньше, так что вы получите что-то работоспособное. По приблизительной оценке, я все же ожидал бы, что вычисление C(15,15,k) займет время, более точно измеренное в часах, чем секундах, но это улучшение по сравнению с O(k), которое заняло бы годы (для k в области 10 ^ 18).
used Используемая здесь свертка (f \ast g)(k) = \sum_{j = 0}^k f(j)*g(k-j).
² Предполагая, что все арифметические операции O (1); если, как и в ОП, требуется только вычет по модулю некоторого M> 0, это верно, если все промежуточные вычисления выполнены по модулю M.