fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long dp[255][5][5][5][5];
  4. const long long MOD=1E9+7;
  5. long long n;
  6. long long f(int ind,int a,int b,int c,int d)
  7. {
  8. 	if(ind==n)
  9. 	{
  10. 		return 1;
  11. 	}
  12. 	if(dp[ind][a][b][c][d]!=-1)
  13. 	return dp[ind][a][b][c][d];
  14. 	long long answ=0;
  15. 	int i,j;
  16. 	if(ind==0||ind==1)
  17. 	{
  18. 		for(i=0;i<4;i++)
  19. 		{
  20. 			answ+=f(ind+1,b,c,d,i);
  21. 			answ=answ%MOD;
  22. 		}
  23. 	}
  24. 	else if(ind==2)
  25. 	{
  26. 		for(i=0;i<4;i++)
  27. 		{
  28. 			if(i!=c)
  29. 			{
  30. 				answ+=f(ind+1,b,c,d,i);
  31. 				answ=answ%MOD;
  32. 			}
  33. 		}
  34. 	}
  35. 	else
  36. 	{
  37. 		for(i=0;i<4;i++)
  38. 		{
  39. 			int isOk=1;
  40. 			if(i!=c)
  41. 			{
  42. 				if(b==0&&c==1&&d==2&&i==3)
  43. 				isOk=0;
  44. 				if(b==1&&c==2&&d==3&&i==0)
  45. 				isOk=0;
  46. 				if(b==2&&c==3&&d==0&&i==1)
  47. 				isOk=0;
  48. 				if(b==3&&c==0&&d==1&&i==2)
  49. 				isOk=0;
  50. 				if(b==0&&c==3&&d==2&&i==1)
  51. 				isOk=0;
  52. 				if(b==3&&c==2&&d==1&&i==0)
  53. 				isOk=0;
  54. 				if(b==2&&c==1&&d==0&&i==3)
  55. 				isOk=0;
  56. 				if(b==1&&c==0&&d==3&&i==2)
  57. 				isOk=0;
  58. 				if(isOk)
  59. 				{
  60. 					answ+=f(ind+1,b,c,d,i);
  61. 					answ=answ%MOD;
  62. 				}
  63. 			}
  64.  
  65. 		}
  66. 	}
  67. 	return dp[ind][a][b][c][d]=answ;
  68.  
  69. }
  70. int main()
  71. {
  72. 	int t;
  73. 	scanf("%d",&t);
  74. 	while(t--)
  75. 	{
  76. 		memset(dp,-1,sizeof(dp));
  77. 		scanf("%lld",&n);
  78. 		long long answ=f(0,0,0,0,0);
  79. 		cout<<answ<<"\n";
  80. 	}
  81. }
Success #stdin #stdout 0s 16480KB
comments (?)
stdin
copy 
5
1
2
3
4
5
stdout
copy 
4
16
48
136
392
https://ideone.com/yrPw7e
language:
C++14 (gcc 8.3)
created:
5 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!