fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. using namespace std;
  5. typedef long long ll;
  6. const int MOD = 1'000'000'007;
  7.  
  8. ll socach(ll n, unordered_map<ll, ll>& mps) {
  9.     if (mps.find(n) != mps.end()) {
  10.         return mps[n];
  11.     }
  12.     if (n == 1) {
  13.         mps[n] = 1; 
  14.     }
  15.     else if (n == 2) {
  16.         mps[n] = 3; 
  17.     }
  18.     else {
  19.         mps[n] = (socach(n - 1, mps) + 2 * socach(n - 2, mps) % MOD) % MOD;
  20.     }
  21.  
  22.     return mps[n];
  23. }
  24.  
  25. int main() {
  26.     int T;
  27.     cin >> T;
  28.     unordered_map<ll, ll> mps;
  29.     for (int i = 0; i < T; i++) {
  30.         ll n;
  31.         cin >> n;
  32.         cout << socach(n, mps) << "\n";
  33.     }
  34.  
  35.     return 0;
  36. }
  37.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin 
3
2
8
12
stdout 
3
171
2731
https://ideone.com/AamClg
language:
C++14 (gcc 8.3)
created:
16 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!