i've written little algorithm calculates series of numbers, big store in unsigned long long. why i've decided take modulo every time next number calculated. function:
#define mod 1000000007 template <typename t> t modpow(t base, t exp, t modulus) { base %= modulus; t result = 1; while (exp > 0) { if (exp & 1) result = (result * base) % modulus; base = (base * base) % modulus; exp >>= 1; } return result; } vector<unsigned long long> b(int n) { vector<unsigned long long> points; vector<unsigned long long> cum_points; points.push_back(0); points.push_back(0); cum_points = points; unsigned long long prev = 0; if (n >= 2){ (int = 0; <= n - 2; i++) { prev += cum_points[i]; prev %= mod; points.push_back((modpow((unsigned long long)2, (unsigned long long)i, (unsigned long long) mod)+prev)%mod); cum_points.push_back((cum_points[i+1]+points[i+2])%mod); } } return points; } this returns vector series of numbers:
0, 0, 1, 2, 5, 12, 28, 64, 144, 320, 704, 1536, 3328, ...
and on...
the problem when n > 50 modulo off: (the first values ones calculated without modulo in code, , values after equal signs results modulo in code.)
50: 1759218604441600 % 1000000007 = 592127074; right answer 51: 3588805953060860 % 1000000007 = 927939229; should be: 927939225 the error gets bit larger every time n gets higher. little offset come from?
some possible problems:
- the
modpow()somehow doesn't give right answer when numbers exceed length. this not problem - there mistake made math, believe used following equations right way:
(a*b) mod c = ((a mod c)*(b mod c)) mod c
(a + b) mod c = ((a mod c)+(b mod c)) mod c
- i have wrong variable type in code, although wouldn't know where.
edit: i've ruled out of possible problems , problem seems lie within calculation of prev when i == 48.
you check whether modulus small enough. have checked size of unsigned long long on system?
std::cout << std::numeric_limits<unsigned long long>::max(); when check that, might check size of unsigned int @ same time. i'm not sure different.
your modulus has 10 digits, product of 2 numbers have 20 digits. if max unsigned long long smaller mod * mod, getting overflow error.
an error in formula show before n = 51.
comments: if using c++11 standard, why not replace macro with
constexpr unsigned long long mod = 1000000007; also, in spot call modpow, avoid casts unsigned long long calling specific function want: modpow<unsigned long long>. arguments converted right type automatically.
