project-euler

https://projecteuler.net/
Log | Files | Refs | README

Euler_76.cpp (824B)

      1 #include "Euler.h"
      2 
      3 ll partition(int n, std::vector<int> &cache)
      4 {
      5     ll p = 0;
      6     std::vector<int> cache_ref = cache;
      7 
      8     if(n >= 0)
      9     {
     10         if(n == 0 || n == 1)
     11         {
     12             return 1;
     13         }
     14         if(cache_ref[n - 1] != 0)
     15         {
     16             return cache_ref[n - 1];
     17         }
     18 
     19         int k = 1;
     20 
     21         ll s1 = 0;
     22         ll s2 = 0;
     23 
     24         while (n - s2 >= 0)
     25         {
     26             s1 = (k * (3 * k - 1)) / 2;
     27             s2 = (k * (3 * k + 1)) / 2;
     28 
     29             int sign = (k - 1) & 1 ? -1 : 1;
     30 
     31             p += sign * partition(n - s1, cache_ref);
     32             p += sign * partition(n - s2, cache_ref);
     33             ++k;
     34         }
     35 
     36         cache_ref[n - 1] = p;
     37     }
     38 
     39     return p;
     40 }
     41 
     42 int Euler::CountingSums()
     43 {
     44     std::vector<int> cache(100, 0);
     45     return partition(100, cache) - 1;
     46 }