I will try to post my.... analysis, which I cannot comprehand now, but: /* https://www.hackerrank.com/challenges/count-ways-1/problem

Task: Little Vadim likes playing with his toy scales. He has N types of weights. The i-th weight type has weight a[i]. There are infinitely many weights of each type. Recently, Vadim defined a function, F(X), denoting the number of different ways to combine several weights so their total weight is equal to X.

Ways are considered to be different if there is a type which has a different number of weights used in these two ways.

For example, if there are 3 types of weights with corresponding weights 1, 1, and 2, then there are 4 ways to get a total weight of 2: Use 2 weights of type 1. Use 2 weights of type 2. Use 1 weight of type 1 and 1 weight of type 2. Use 1 weight of type 3. Given N, L, R, and a[1], ..., a[N] can you find the value of F(L) + F(L+1) + ... + F(R)?

Input Format: The first line contains a single integer, N, denoting the number of types of weights. The second line contains N space-separated integers describing the values of a[1], a[2] ..., a[N] respectively The third line contains two space-separated integers denoting the respective values of L and R.

Constraints 1 ≤ N ≤ 10 0 < a[i] ≤ 10**5 ∏ a[i] ≤ 10**5 1 ≤ L ≤ R ≤ 10**17

Note: The time limit for C/C++ is 1 second, and for Java it's 2 seconds.

Output Format Print a single integer denoting the answer to the question. As this value can be very large, your answer must be modulo 10**9+7 (, which is prime number... 10**9+9 as well).

Sample Input . . . . . . . . 3 1 2 3 1 6 . . . . . . . . Sample Output 22 Explanation F(1) = 1 F(2) = 2 F(3) = 3 F(4) = 4 F(5) = 5

F(6) = 7

Sample Input . . . . . . . . 3 1 1 2 2 2 . . . . . . . . Sample Output

4

Sample Input . . . . . . . . 1 9 34297 65495 . . . . . . . . Sample Output

3467

Sample Input . . . . . . . . 5 1 7 8 2 3 71530 82750 . . . . . . . . Sample Output

53695086

Sample Input . . . . . . . . 6 5 15 2 9 4 6 8405783146404694 14942384943008793 . . . . . . . . Sample Output

500331227

Modulo arithmetics shall be in place... Especially division for prime M = 10**9+7. Hey. Divisioon table on circle M is of M**2 size. It will take big chunk of all addressable space on 64-bit computer: positive Integer is about 2*10**9; positive Long is approximately 8*10**18; Grrr.

26.12.2018. Подход. Дано............................................................................................................................................. 01. N - размер разновеса - количество типов гирек. 02. Разновес: WN = W[N] = {w[i]}, 1 <= i <= N, где w[i] - вес гирек и-того типа. Развитие темы.................................................................................................................................... 03. Определение. F(X) = F(X, W) - количество вариантов взвешивания веса Х по разновесу W. 04. Определение. Vk = V[k] = w[1]*...*w[k] - общее кратное разновеса от 1 до k; Къ примеру V[1] = w[1], V[N] = w[1]w[2]...*w[N] 05. Лемма. Любой X можно представить как X = m*V + r[V], где m, V, r=rV=r[V] - целые, 0 <= r < V; Наблюдения....................................................................................................................................... 06. F(X, W[к]) = ∑F( X-w[к]*j, W[к-1] ), 0 <= j <= X/w[к]; Сумма вариантов взвешивания по разновесу W[к-1], когда вес равен изначальному минус вес j гирек типа к. 07. F(0) = 0; Несуществующий груз можно взвесить одним способом: ни одной гирьки. 08. Теорема. (Доказывается по индукции на основе 06 и 07). F(X, WN) = F( (m*VN + rN), WN ) - полигном степени N-1 по m,... более того F(X, WN) = F( (m*VN + rN), WN ) = ∑(a[i]*m**i)/(N-1)!, 0 <= i < N, где все a[i] - целые, a[0]/(N-1)! = F(rN); 08.1. На самом деле требуется ещё один шаг помимо 06 и 07. Найдите сами. 09. (Рекурсивно). Если для произвольно взятого К мы сможем посчитать количество взвешиваний для всех 0 <= m < К, то получим систему линейных уравнений относительно коэффициентов уравнения (08). А, стало быть, по рекурсии, сможем быстро просчитать количество взвешиваний для (08) и К+1. Отступление...................................................................................................................................... 10. Задача 1. Научится решать систему линейных уравнений по модулю М [= 10**9+7]. 10.0. r = X%M - остаток от деления по модулю М. 10.1. (A + B)%M = (a*M+r(A) + b*M+r(B))%M = (r(A) + r(B))%M 10.2. (A - B)%M = (a*M+r(A) - b*M+r(B) + M)%M = ( r(A) + (M - r(B)) )%M 10.3. (A * B)%M = ( (a*M+r(A)) * (b*M+r(B)) )%M = (r(A) * r(B))%M 10.4. Операцией деления по модулю займёмся позже, если потребуется (найти х если а=б*х, а и б известны по модулю М) Наблюдения....................................................................................................................................... 11. Если все w[i] = d*v[i] , то F(X, W) = {F(X/d, V), X%d = 0 | 0, X%d ≠ 0}... въ дальнейшем будем предполагать, что d = 1. Очевидно, да? 12. По (06) ∑F(x, W), 0 <= x <= X равна F(X, U), где U = {1, W}. 13. Стало быть ∑F(x, W), L <= x <= R равно F(R, U) - F(L-1, U), вот. 14. Переформулировка (08): ∑a[i]*m**i = k! * F( (m*V[k+1] + r[V[k+1]]), W[k+1] ) по 0 <= i <= k; 14.1. (14) - это выражение уравнений (08) въ целочисленном виде. Зная m**i и k!*F( (m*V[k+1] + r[V[k+1]]), W[k+1] ) для 0 <= m <= k получим систему уравнений для нахождения a[i]; Переобозначения.................................................................................................................................. 15. Коэффициенты a[i] въ уравнениях (08), (14) зависят от V[k+1] - остатка от деления нацело. То есть a[i, r]... Для каждого r свой набор a[i], 0<=i<К. 16. G(X, W[K+1]) = K!*F(X, W[K+1]). Вычисление a[i, r] удобнее въ терминах G - целочисленные уравнения (по модулю М, если надо) 17. Итак, G(X, W[K+1]) = K!*F(X, W[K+1]) = ∑a[i, r[V[K+1]]]*m**i, при m = X/V[K+1], смотри (05), (08); 18. Рекурсивные уравнения (09) теперь выглядят так: ∑a[i, r[V[K+1]]]*m**i = G(m*V[K+1] + r[V[K+1]], W[K+1]) = K! * F(m*V[K+1] + r[V[K+1]], W[K+1]); теперь, F(m*V[K+1] + r[V[K+1]], W[K+1]) = F(Y, W[K+1]), где Y = m*V[K+1] + r[V[K+1]]; а из (06) F(Y, W[K+1]) = ∑F( Y-w[K+1]*j, W[K] ) = 1/(K-1)! * ∑(K-1)!*F( Y-w[K+1]*j, W[K] ) = 1/(K-1)! * ∑G( Y-w[K+1]*j, W[K] ); то есть G(Y, W[K+1]) = K * ∑G( Y-w[K+1]*j, W[K] ), 0 <= j <= Y/w[K+1]; 18.1. По честному, можно загуглить и найти формулы для ∑n**k и съ-оптимизировать вычисление G(Y, W[K+1]) = K * ∑G( Y-w[K+1]*j, W[K] ), 0 <= j <= Y/w[K+1], ведь G( X, W[K] ) = ∑a[i, К]*m**i, при m = X/V[K]... и применить ∑n**k... Поскольку а) вычисление значения полигнома степени N ≈ 2*N операций: a[0] + x*(a[1] + x*(...)); б) таких иксов всего Y/w[K+1], то есть ~ m*V[К] - то и оптимизировать незачем (другое дело, что надо бы разновес отсортировать... по применяемому алгорифму: по возрастанию весов или наоборот). Оценки........................................................................................................................................... 18.2. Вспомним некоторые ограничения: а. 0 < w[i] <= 10**5 б. w[1]*...*w[N] <= 10**5 в. 0 < N <= 10 18.3. а так же, что мы пытаемся построить систему К линейных уравнений G(V[K]*m + r[V], W[K]) = (K-1)*F(V[K]*m + r[V], W[K]), 0 <= m < K; 18.4. таким образом, ~ m*V[К] из (18.1) может быть равно 10*10**5... при m=10, V[К]=10**5 и w[K+1]=1. Мне эта цифра не нравится. А вот если w[K+1]=10**5, то V[К]=1 и ~ m*V[К] = 10, что легко суммируется безо всякой оптимизации. 18.5. В общем и целом цифра 10**6*2*10 меня не очень пугает - 0.01 секунды на моём компьютере - 10 таких уравнений (для всех К от 1 до 10) = 0.1 секунды Отсортируем w[i] по возрастанию весов: w[1] <= w[2] <= ... <= w[N]. Каково наименьшее w[N] при условии 18.2.б? Четыре. Наибольшее V[К] = 25000. Небольшое улучшение, но всё же. Кстати, 3**9 = 19683, 4*3**8 = 26244; Продолжим........................................................................................................................................ 18.6. Итак, все a[i, r[V]], 0 <= K <= N, 0 <= i <= K вычисляются за 0.02 секунды... точнее все уравнения x[i, r[V]]a[i, r[V]] = y[i, r[V]] mod M. Из малой теоремы Ферма 1/a = a*(M-2) mod M; a[i, r[V]] = y[i, r[V]] * 1/x[i, r[V]] 18.7. Задача 2. Надо научиться быстро возводить число в очень большую степень (2**29 < 10**9 + 5 < 2**30)... х(М-2) = ? а. Разложим (М-2) по степеням 2: М-2 = ∑bit[i]*2**i, 0 <= i <= 29, bit[i] = {0, 1} б. Посчитаем следующие степени х: х = х(2**0), х2 = х(2**1), х4 = х(2**2), х8 = х(2**3),..., х(2**29) последовательным возведением в квадрат. х(М-2) = П х**(2**i), 0 <= i <= 29 и bit[i] = 1. ≈60 умножений или 2*lg(M). в. Есть и другие алгоритмы быстрого возведения в большую степень того же порядка сложности. Что получилось?.................................................................................................................................. 19. а. умеем складывать, вычитать, умножать и делить на кольце по модулю М б. умеем решать систему линейных уравнений на кольце по модулю М в. умеем вычислять значение полинома на кольце по модулю М. Это умение будет использоваться гораздо чаще, чем два предыдущих, на текущем алгоритме г. придётся вычислить a[i, r[V]] для всех G(r[V], W[K])... до 25000 штук наборов... д. G(X) mod M = G(x*M + r(X)) mod M = G(r(X)) mod M. е. G(r[V[N+1]], W[N+1]) = N!*F(r[V[N+1]], W[N+1]) mod M. ==> ответ F вычисляется по (19.а) Всё.............................................................................................................................................. 20. Уточнения будут прокомментированы по ходу исполнения. Ожидается, что будут ошибки типа ±1 и true/false Жопа 29.12.2018.................................................................................................................................. 21. Полное исполнение выше проанализированного не случилось (попытка сделана 27.12.2018-го). Из-за лени... или не хватило времени... Так или иначе - мне повезло ;о) Исполненные (не все были закодированы) алгорифмы работают - это хорошо. А так... Въ проблеме существует куча краевых случаев и... линейный подход хорош для одного из них... 21.1. Не до конца оцененный вариант w = {3,3,3,3,3,3,3,3,4,4,} пропустил фактор порядка 3000-4000, а это час вместо секунды. Переосмысление................................................................................................................................... 22. (06) и (18) разделяют проблему на сумму произведений по выборке вариантов взвешивания веса Y гирьками w[K+1] (, что либо 0, либо 1) по 0 <= Y <= X и вариантов взвешивания веса X-Y гирьками разновеса W[K] = W[K+1]\w[K+1]. 23. Обобщение (06) и (18) - разделяй и властвуй... Разобьём разновес W[N] на два (в общем случае - несколько, что оставим для других) под-разновеса величиной K и N-K (W[K] и W[N-K]) пока что не уточняя ни величину К, ни какие типы гирек из W[N] попали въ W[K] (W[N-K] = W[N]\W[K]). Для данного веса Х, количество вариантов взвешивания по W[N] равно сумме произведений взвешивания Y по разновесу W[K] и X-Y по W[N-K]. 23.1. А зачем всё это? Переопределённая постановка задачи посчитать разницу F(R, W[N+1]) - F(L-1, W[N+1]); по модулю М. F(X, r(X,V)) - полигном степени N. Нам, собственно, требуется знать коэффициенты двух уравнений: F(R, r(R,V)) и F(L, r(L,V)); Для этого надо решить пару систем линейных уравнений (18). F(X, r(X,V)) = F(V*m + r(X,V), r(X,V)) = ∑a[i, r]*m**i; Чтобы найти N+1 коэффициентов a[i, r] надо построить N+1 уравнений, то есть найти значения F(V*m + r(X,V), r(X,V)) для 0 <= m <= N. 23.2. Разделение (06) - это нули и единицы по под-разновесу {w[N+1]} и F(X, W[N]) по под-разновесу W[N] = W[N+1]\w[N+1]. Разделение (23) - это F(X, W[K]) по под-разновесу W[K] и F(X, W[N+1-K]) по под-разновесу W[N+1-K] = W[N+1]\w[K]. (06) - частный случай (23). Утоньчённые оценки............................................................................................................................... 24. На пальцах... Для дипломной работы - только намёки... Чтобы посчитать F(X, W[K]) для произвольного Х... требуется знать V[K]=Пw[i], 1<=i<=K наборов коэффициентов для полигномов степени К. То есть надо знать (К+1)*V[K] чисел. Чтобы их получить надо решить V[K] систем уравнений порядка (К+1). А для этого надо посчитать (К+1)*V[K] правых частей. По (06), каждая из этих правых частей считается за V[K-1]2К операций... Это почему я предложил отсортировать W[N] по возрастанию... см. (18.5) 24.1. Линейный подход (06), рекурсивно, уменьшает К на единицу, а V[K] въ w[К] раз. (21.1) показывает, что [грубо, конечно] в определённых случаях шаг линейного подхода порядка О( (К+1)*V[K]**2 ), где V[K] уменьшается, примерно, въ 3 раза... или пошаговая сложность задачи упрощается въ 10 раз. Первый (из 10) шаг порядка О(10*20000**2) операций, где О>20... то есть О(4*10**9) или ≥ 10**11... оптимистически. 24.2. (23), с другой стороны, разбивает задачу N + V[N] на две подзадачи (в идеальном случае) N/2 + sqrt(V[N])... что на первом шаге даёт порядок сложности О( 2*(0.5*N*V[N]) )... Для (21.1) это О(10**6) или ≥ 10**7... То есть ускорение въ 2500 явно на лице. Что теперь? ..................................................................................................................................... 25. Задача 3. Разбить разновес W[N] на W[К] и W[N-К] так, чтобы V[K] и V[N-К] были как можно ближе къ sqrt(V[N]) 25.1. W[N] может содержать несколько w[i]=1. Они не влияют на решение (25)... но повлияют на К и N-К... Единичные веса надо распределить так, чтобы уменьшить К*V[K] + (N-К)*V[N-К] 25.2. Вполне возможно, что в оценках цифру N нужно заменить на N**2, то есть для (24.1) это О( K**2 * V[K]**2 ), а для (24.2) - О( K**2 * V[K] ). Тогда в (25.1) надо оптимизировать К**2*V[K] + (N-К)**2*V[N-К]... 26. Прикидки решения (25.*). Подход очень напоминает "быструю сортировку": шаг №1. Выбрать опорное значение = sqrt(V[N]) и, например посчитав все 2**N частных произведений весов разновеса W[N] выбрать ту пару, что ближе всего къ опорному значению, то есть V[K]+V[N-К] минимально. Или как-нибудь ещё... шаг №2. Если V[K] и V[N-К] отклоняются (относительно) от опорного значения не больше чем на, скажем, 50%, то считается, что они, ... равны. В этом случае распределить единицы (25.1) поровну между V[K] и V[N-К]... лишнюю отдать меньшему из V[K] и V[N-К]... Иначе все отдать меньшему. А можно и перебором, как на №1. Посмотрим, как карта ляжет. На сегодня всё................................................................................................................................... */

Here is Counting the Ways problem solution in Python Java C++ and C programming - https://programs.programmingoneonone.com/2021/07/hackerrank-counting-the-ways-problem-solution.html

It's similar to the coin change dp problem.

can not understand the question what is required?

anyone can tell me how can create a programe for this ...! (python 3)