Question

Solutie recursiva pentru

Se dă un număr natural N. Să se calculeze expresia:

E=(2^0+2^1+2^2+2^3+…+2^N)%1000000007
unde x % y reprezintă restul împărţirii lui x la y.

Date de intrare
Fișierul de intrare sume1.in conține pe prima linie numărul N.

Date de ieșire
Fișierul de ieșire sume1.out va conține pe prima linie rezultatul expresiei E.

Restricții și precizări
1 ≤ N ≤ 1017
1000000007 este număr prim.
Pentru 30% din teste, N ≤ 106
Exemplul 1
sume1.in

4
sume1.out

31
Exemplul 2
sume1.in

9
sume1.out

1023

Answer 1

#include <fstream> using namespace std; ifstream fin("sume1.in"); ofstream fout("sume1.out"); #define MOD 1000000007 long long N; long long rise(long long base, long long power) { if(power == 0) { return 1; } long long x = rise(base, power / 2); if(power % 2 == 0) { return (x * x) % MOD; } return (((x * x) % MOD) * base) % MOD; } int main() { fin >> N; fout << (rise(2, N + 1) + MOD - 1) % MOD << '\n'; fin.close(); fout.close(); return 0; }