fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define enter cout<<"\n"
  5. #define int  long long  
  6. #define vi vector<int>
  7. #define vl vector<ll>
  8. #define pii pair<int,int>
  9. #define pll pair<ll,ll>
  10. #define MOD 1000000007
  11. #define MAXM 1000000
  12.  
  13. void fastIO()
  14. {
  15.     ios_base::sync_with_stdio(false);
  16.     cin.tie(NULL);
  17. }
  18.  
  19.  
  20. void display(vector<vector<char>> &v, int n, int m) 
  21. {
  22.     for(int i=0; i<n; i++) {
  23.         for(int j=0; j<m; j++) {
  24.             cout<<v[i][j];
  25.         } enter;
  26.     }
  27. }
  28.  
  29. int n;
  30.  
  31. // vector<vector<int>> adj;
  32. // vector<int>depth, size, inc;
  33. // int dfs(int c, int p)
  34. // {
  35. //     depth[c] = depth[p] + 1; size[c] = 1;
  36. //     for(int i=0; i<adj[c].size(); i++) {
  37. //         if(adj[c][i] == p) continue;
  38. //         size[c] += dfs(adj[c][i], c);
  39. //     }
  40. //     inc[c] = size[c] - depth[c]; return size[c];
  41. // }
  42.  
  43. vector<int> dpLast;
  44. void solve()
  45. {
  46.     fastIO();
  47.     cin>>n;  
  48.     dpLast = vector<int>(2, 0);
  49.     dpLast[1] = 1;
  50.     vector<int> dpNew(2,0);
  51.     for(int i=1; i<=n; i++) {
  52.         dpNew[0] = (2*dpLast[0] + dpLast[1])%MOD;
  53.         dpNew[1] = (3*dpLast[0])%MOD;
  54.         dpLast = dpNew;
  55.     } 
  56.     cout<<dpLast[1]; enter;
  57. }
  58. int32_t main()
  59. {
  60.     solve();
  61.     return 0;
  62. }
Success #stdin #stdout 0s 4856KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/8aooO3
language:
C++14 (gcc 8.3)
created:
3 years 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!