90% (149ms) C++ solution following Google C++ Style Guide with Parallelization
Motivation\n\nLets implement fast C++ solution based on DP sticking to the Google C++ Style Guide. We will have a look at rules which make our code readable and
# Motivation\n\nLets implement fast C++ solution based on DP sticking to the [Google C++ Style Guide](https://google.github.io/styleguide/cppguide.html). We will have a look at rules which make our code readable and robust. Also, we will try to use modern C++ constructions. In the end we will look into a parallelization opportunity in our code and how to leverage modern C++ Extention for Parallelizm.\n\n# Intuition\n\nFor each number `value` we would like to know how many occurancies `count` it has in the input array.\n\nIf we maintain an array `reached` in which `reached[summ]` is the number of ways to construct `summ` using previous numbers, then we can say that the new amount of ways in the `new_reached[summ]` will be a summ of the ways using none of the new values, one, two, ... `count`.\n\nTo generate the output - we will have to find a summ of values in the `reached` array from `left` to `right`.\n\n# Approach\n\nWe will introduce a constant to keep our modulo value. According to the [Constant Names](https://google.github.io/styleguide/cppguide.html#Constant_Names) rules it should be named something like `kModulo`.\n\n[Function names](https://google.github.io/styleguide/cppguide.html#Function_Names) requires to have first capital letter in the names of functions. Due to the platform requirements we will have to ignore this rule. But to stay concistent - we will name other functions using camelCase with the first lower letter.\n\nFrom the [General Naming Rules](https://google.github.io/styleguide/cppguide.html#Function_Names) we can see that the names of the variables (and other names) should be optimized for readability. We can rename input parameters of our function to match this rule better.\n\n[Write Short Functions](https://google.github.io/styleguide/cppguide.html#Write_Short_Functions) forces us to break our future code into smaller pieces. This also lets us design our main algorithm in the main function and add details in the functions.\n\nWe will break out two functions:\n\n1. Calculating `frequences` of the values in the input array\n2. Propagating some `value` with the given `offset` in the `new_reached` array.\n\nAccording to the [Inputs and Outputs](https://google.github.io/styleguide/cppguide.html#Inputs_and_Outputs) rule first function will const reference to the input numbers and return an `std::map<int, int>` ([Namespaces](https://google.github.io/styleguide/cppguide.html#Namespaces) rule does not allow us to skip `std::` prefix). According to the new C++ rules this will not introduce copy in the place where we will use it.\n\nThe `propagateNumber` function will have multiple parameters and one output parameter `new_reached`. It should be last and passed by reference, because it is not optional.\n\n[Looping and branching statements](https://google.github.io/styleguide/cppguide.html#Formatting_Looping_Branching) forces us to put a space after the statement keyword (`if`, `for`). Usually we should wrap the body of the loop or a branch into braces, but there is also an exception for smaller pieces of code, which we are going to use in our solution.\n\n# Code\n```\nconstexpr int kModulo = 1000000007;\n\nstd::map<int, int> buildFrequences(const std::vector<int>& nums) {\n    std::map<int, int> frequences;\n    for (int value : nums) ++frequences[value];\n    return frequences;\n}\n\nvoid propagateNum(\n        int value, int count, int offset, int right,\n        const std::vector<int> &reached,\n        std::vector<int> &new_reached) {\n    new_reached[offset] = reached[offset];\n    long long summ = reached[offset];\n    int front = offset + value;\n    int current_count = 1;\n    while (front <= right) {\n        summ += reached[front];\n        if (summ >= kModulo) summ -= kModulo;\n        new_reached[front] = summ;\n        ++current_count;\n        if (current_count > count) {\n            summ -= reached[front - count * value];\n            if (summ < 0) summ += kModulo;\n        }\n        front += value;\n    }\n}\n\nclass Solution {\npublic:\n    int countSubMultisets(std::vector<int>& nums, int left, int right) {\n        // Check Input data for correctness.\n        if (nums.size() == 0) return 0;\n        if (left > right) return 0;\n        if (left < 0) return 0;\n\n        std::map<int, int> frequences = buildFrequences(nums);\n        std::vector<int> reached(right + 1);\n        std::vector<int> new_reached(right + 1);\n        reached[0] = frequences[0] + 1;\n        for (const auto &[value, count] : frequences) {\n            if (value == 0) continue;\n            if (value > right) continue;\n            for (int offset = 0; offset < value; ++offset) {\n                propagateNum(value, count, offset, right, reached, new_reached);\n            }\n            std::swap(reached, new_reached);\n        }\n        int res = 0;\n        for (int ind = left; ind <= right; ++ind) {\n            res = (res + reached[ind]) % kModulo;\n        }\n        return res;\n    }\n};\n```\n\n# Parallelizing the solution\n\nIn the main body we have an opportunity for the paralellization. just replace the the loop which wraps the `propagateNum` function call with this code:\n\n```\n#include <execution>\n// ...\nstd::vector<int> steps(value);\nfor (int step = 0; step < value; ++step) steps[step] = step;\nstd::for_each(\n    std::execution::par_unseq, steps.begin(), steps.end(), \n    [this, value, count, right, &reached, &new_reached](int step) {\n        this->propagateNum(value, count, step, right, reached, &new_reached);\n    });\n```\n\nThis propagations do not intersect and can be run in parallel using up to `value` cores.\n\nI am using g++ on WSL:\n\n```\ng++ -O3 --std=c++17 main.cc -pthread -ltbb\n```\n\nI had to install `libtbb` to be able to use C++ paralellization.\n\nWith the big enough input and the `-O3` optimizations parallel solution was almost 4 times faster than the simple one.
['Dynamic Programming', 'C++']