Advertisement
mickypinata

AJJak-T005: Tiling-04

Dec 4th, 2021
775
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long lli;
  5.  
  6. const int N = 1000 + 5;
  7. const int MD = 1e9 + 7;
  8.  
  9. int dp1[N], dp2[N];
  10.  
  11. int main(){
  12.  
  13.     int n;
  14.     scanf("%d", &n);
  15.     dp1[1] = 1;
  16.     dp2[1] = 1;
  17.     for(int i = 2; i <= n; ++i){
  18.         dp1[i] = (4 * (lli)dp1[i - 1] + dp2[i - 1]) % MD;
  19.         dp2[i] = (2 * (lli)dp2[i - 1] + dp1[i - 1]) % MD;
  20.     }
  21.     cout << (dp1[n] + dp2[n]) % MD;
  22.  
  23.     return 0;
  24. }
  25.  
Advertisement
RAW Paste Data Copied
Advertisement