Cerinta completa

Little Walter likes playing with his toy scales. He has types of weights. The weight type has weight . There are infinitely many weights of each type.

Recently, Walter defined a function, , denoting the number of different ways to combine several weights so their total weight is equal to . 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 types of weights with corresonding weights , , and , then there are ways to get a total weight of :

  1. Use weights of type .
  2. Use weights of type .
  3. Use weight of type and weight of type .
  4. Use weight of type .

Given , , , and , can you find the value of ?

Input Format

The first line contains a single integer, , denoting the number of types of weights.
The second line contains space-separated integers describing the values of , respectively
The third line contains two space-separated integers denoting the respective values of and .

Constraints

Note: The time limit for C/C++ is second, and for Java it’s 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 .

Sample Input

3
1 2 3
1 6

Sample Output

22

Explanation






Limbajul de programare folosit: cpp14

Cod:

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

int n;
int a[10];
long long L, R;

const int N = 202000;
int dp0[N];
int dp1[N];

inline void add(int &x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
}

long long solve(long long v) {
    bitset<62> s(v);
    memset(dp0, 0, sizeof(dp0));
    dp0[0] = 1;

    for (int k = 0; k < 62; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = N - a[i] - 1; j >= 0; j--) {
                add(dp0[j + a[i]], dp0[j]);
            }
        }
        if (s[k]) {
            add(dp0[0], dp0[1]);
            for (int i = 1; i < N - 1; i++) {
                dp0[i] = dp0[i + 1];
            }
        }
        memset(dp1, 0, sizeof(dp1));
        for (int i = 0; i < N; i++) {
            add(dp1[(i + 1) / 2], dp0[i]); 
        }
        swap(dp0, dp1);
    }

    return dp0[0];
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> L >> R;

    int ans = solve(R) - solve(L - 1);
    if (ans < 0) ans += MOD;
    cout << ans << endl;
}

Scor obtinut: 1.0

Submission ID: 464649173

Link challenge: https://www.hackerrank.com/challenges/count-ways-1/problem

Counting the Ways