fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. using namespace std;
  4. #define MOD 1000000007
  5. int dp[100005][3][4]= {0};
  6. int main() {
  7.     int n;
  8.     cin >> n;
  9.     dp[1][0][1] = 1;
  10.     dp[1][2][0] = 1;
  11.     for(int i=2; i<=n; i++){
  12.         if(i&1){
  13.         	dp[i][2][0] = dp[i-1][2][0];
  14.             dp[i][0][1] = dp[i-1][2][0];
  15.             dp[i][2][1] = (dp[i-1][0][1] + dp[i-1][2][1]);
  16.             dp[i][1][3] = dp[i-1][1][3];
  17.             dp[i][2][2] = (dp[i-1][1][2] + dp[i-1][2][2])%MOD;
  18.             dp[i][0][3] = ((dp[i-1][1][2] + dp[i-1][2][2])%MOD + (dp[i-1][1][3] + dp[i-1][0][3])%MOD)%MOD;
  19.         }
  20.         else {
  21.             dp[i][2][0] = dp[i-1][2][0];
  22.             dp[i][1][2] = dp[i-1][2][0];
  23.             dp[i][2][1] = (dp[i-1][0][1] + dp[i-1][2][1]);
  24.             dp[i][1][3] = ((dp[i-1][0][1] + dp[i-1][2][1])%MOD + (dp[i-1][1][3] + dp[i-1][0][3])%MOD)%MOD;
  25.             dp[i][2][2] = (dp[i-1][1][2] + dp[i-1][2][2])%MOD;
  26.             dp[i][0][3] = dp[i-1][0][3];
  27.         }
  28.         // for(int j=0;j<=2;j++){
  29.         // 	for(int k=0;k<=3;k++){
  30.         // 		if(dp[i][j][k])
  31.         // 			printf("i=%d j=%d k=%d dp=%d\n",i,j,k,dp[i][j][k]);
  32.         // 	}
  33.         // }
  34.     }
  35.     int p = 1;
  36.     for(int i=1; i<=n; i++){
  37.     	p = (p*2) % MOD;
  38.     }
  39.     p = (p - dp[n][0][3] - dp[n][1][3] )%MOD;
  40.     p = (p+MOD)%MOD;
  41.     cout << p << endl;
  42.     return 0;
  43. }
Success #stdin #stdout 0s 20752KB
comments (?)
stdin
copy 
10
stdout
copy 
803
https://ideone.com/ZLRoIl
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!