Simplify your hash function

If you know the hash key is a combination of a 32-bit integer and a 16-bit integer, you can pack them together in a 64-bit integer and avoid having to create a custom hash function:

std::unordered_map<std::uint64_t, boost::multiprecision::cpp_int> hmap;

boost::multiprecision::cpp_int F(std::uint32_t n, std::uint16_t k) {
    // skip branches
    if(k == 1 && n >= 1)
        return 1;

    if(k > n || n <= 0 || k <= 0) 
        return 0;

    // check the cache first
    std::uint64_t key = n | std::uint64_t(k) << 32;

    if(auto it = hmap.find(key); it != hmap.end())
        return it->second;

    // recurse
    return hmap[key] = F(n - k, k) + F(n - k, k - 1);
}

This also ensures that the key is guaranteed to be unique, whereas your hash function might cause two distinct pairs of n and k to be hashed to the same value, which is not what you want! Especially on a 32-bit system, your hash function could likely already have seen collisions for n = 30000. You can use a custom hash function like that, but then you have to pass it as an extra template parameter to the declaration of hmap.

Avoiding recursion

The on-line encyclopedia of integer sequences lists several different ways to calculate A111133, some are just sums that can be implemented with a simple for-loop without using any recursion. However, these sums might involve very large numbers, which will probably make it slower than the more simple addition of two recursive calls.

We can further simplify the recursive function and reduce the total number of requests to our cache like this

#include <iostream>
#include <unordered_map>
#include <cstdint>
#include <boost/multiprecision/cpp_int.hpp>

constexpr std::size_t hash(std::uint32_t lhs, std::uint32_t rhs) noexcept {
    static_assert(sizeof(std::size_t) != 64);
    return static_cast<std::size_t>(lhs) << 32 | rhs;
}

using BigInt = boost::multiprecision::cpp_int;

std::unordered_map<std::size_t, BigInt> dp;

BigInt partitions(std::uint32_t n, std::uint32_t k) {
    if (std::uint_fast64_t(k) * (k + 1) / 2 > n)
        return 0;

    if (k == 1)
        return 1;

    auto& value = dp[::hash(n, k)];
    if (value == 0)
        value = partitions(n - k, k) + partitions(n - k, k - 1);
    return value;
}

int main()
{       
    std::uint32_t n = 30000;
    BigInt total = 0;
    for (std::uint32_t k = 2; std::uint_fast64_t(k) * (k + 1) / 2 <= n; ++k)
      total += partitions(n, k);        
    std::cout << total << '\n';
    return 0;
}

It suffices to verify the condition k * (k + 1) / 2 <= n that there exists at least one partition of n into k distinct natural numbers.

Some rough time estimates:

• n = 30000 mine: 3119ms, yours: 4252ms;
• n = 100000 mine: 22228ms, yours: 35023ms;
• n = 300000 mine: 484719ms. I didn't check your solution because I wasn't sure whether the time and memory requirements scale acceptably. Mine required about 12GB at peak and became runnable only after tweaking stack size in the project settings and expanding swap size appropriately. But honestly, I didn't wait for my program to finish, only grabbed the computations result.

I need to calculate input that is max 300 000

4210862274208599320132457681361205631766332745531366097251182523840271778374041776996777544268557708791556972634240204931182275636709667458901634960056418648460211352341024814062465102985788332978802711358792090676627722144184552304071441127403307150949156714152542445860792515401696279114099266905863851501599751992437947170596759659111476740607340695732652666851170071652280194048602757002299800991344524743320843401058188959