fork download
copy 
  1. /// no time to waste
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. const int MX = 1e5 + 7;
  6. const int MOD = 1e9 + 7;
  7. int n;
  8. long long dp[MX][4][2];
  9. /// dp[i][j][k] : số lượng số may mắn độ dài i, kết thúc bằng số j, và tổng % 2 đang là k
  10. /// i = [0...n]  |  j = [1...3]  |  k = [0, 1]
  11.  
  12. int32_t main() {
  13.     ios::sync_with_stdio(false);
  14.     cin.tie(0), cout.tie(0);
  15.     freopen("mayman.inp", "r", stdin);
  16.     freopen("mayman.out", "w", stdout);
  17.  
  18.     cin >> n;
  19.     dp[1][1][1] = dp[1][3][1] = dp[1][2][0] = 1;
  20.     for(int i=2;i<=n;i++) {
  21.         for(int j=1;j<=3;j++) {
  22.             for(int last_number = 1; last_number <= 3; last_number++) {
  23.                 if(last_number == j && j == 3) {
  24.                     continue;
  25.                     /// đề không cho 2 số 3 cạnh nhau
  26.                 }
  27.  
  28.                 for(int k=0;k<2;k++) {
  29.                     int new_sum_mod_2 = (k + j) % 2;
  30.                     dp[i][j][new_sum_mod_2] += dp[i - 1][last_number][k];
  31.                 }
  32.             }
  33.             dp[i][j][0] %= MOD;
  34.             dp[i][j][1] %= MOD;
  35.         }
  36.     }
  37.  
  38.     cout << (dp[n][1][0] + dp[n][2][0] + dp[n][3][0]) % MOD;
  39.     return 0;
  40. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
2
stdout
copy 
Standard output is empty
https://ideone.com/mVX2yc
language:
C++ (gcc 8.3)
created:
1 day 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!