fork download 
  1. #include <cstring>
  2. using namespace std;
  3.  
  4. int mat[9][9] =  // constructing matrix column by column
  5.  {{0,0,0,0,1,0,0,0,0},
  6.   {4,0,0,0,0,0,1,0,0},
  7.   {0,2,0,0,0,0,0,1,0},
  8.   {0,1,0,0,0,0,0,0,0},
  9.   {0,0,2,2,0,0,0,0,0},
  10.   {0,0,1,0,0,0,0,0,1},
  11.   {0,0,0,0,2,2,0,0,0},
  12.   {0,0,0,0,0,0,1,0,0},
  13.   {0,0,0,0,0,0,0,1,0}};
  14.  
  15. int one[9][9] =  // 
  16.  {{1,0,0,0,0,0,0,0,0},
  17.   {0,1,0,0,0,0,0,0,0},
  18.   {0,0,1,0,0,0,0,0,0},
  19.   {0,0,0,1,0,0,0,0,0},
  20.   {0,0,0,0,1,0,0,0,0},
  21.   {0,0,0,0,0,1,0,0,0},
  22.   {0,0,0,0,0,0,1,0,0},
  23.   {0,0,0,0,0,0,0,1,0},
  24.   {0,0,0,0,0,0,0,0,1}};
  25.  
  26. int zero[9][9] =  // 
  27.  {{0,0,0,0,0,0,0,0,0},
  28.   {0,0,0,0,0,0,0,0,0},
  29.   {0,0,0,0,0,0,0,0,0},
  30.   {0,0,0,0,0,0,0,0,0},
  31.   {0,0,0,0,0,0,0,0,0},
  32.   {0,0,0,0,0,0,0,0,0},
  33.   {0,0,0,0,0,0,0,0,0},
  34.   {0,0,0,0,0,0,0,0,0},
  35.   {0,0,0,0,0,0,0,0,0}};
  36.  
  37.  
  38. const int mod = 1000000007;
  39.  
  40. class matrix { public:
  41. 	int a[9][9];
  42.  
  43. 	void take(int mt[9][9])
  44. 	{
  45. 		for (int i=0;i<9;++i)
  46. 			for (int j=0;j<9;++j)	
  47. 				a[i][j] = mt[i][j];
  48. 	}
  49.  
  50. 	void operator = (matrix b)
  51. 	{
  52. 		for (int i=0;i<9;++i)
  53. 			for (int j=0;j<9;++j)	
  54. 				a[i][j] = b.a[i][j];
  55. 	}
  56.  
  57. 	matrix operator * (matrix b)
  58. 	{
  59. 		matrix c; c.take(zero);
  60. 		for (int i=0;i<9;++i)
  61. 			for (int j=0;j<9;++j)
  62. 				for (int k=0;k<9;++k)
  63. 					c.a[i][j] = (  1LL * c.a[i][j] + 1LL * a[i][k] * b.a[k][j] ) % mod;
  64. 		return c;
  65. 	}
  66. }; 
  67.  
  68. matrix pow(matrix a,long long pw)
  69. {
  70. 	if ( pw == 0 ) 
  71. 	{
  72. 		matrix out;
  73. 		out.take(one);
  74. 		return out;
  75. 	}
  76.  
  77. 	matrix out = pow(a,pw/2);
  78. 	out = out * out;
  79. 	if ( pw % 2 ) out = out * a;
  80.  
  81. 	return out;
  82. }
  83.  
  84. class Chimney { public:
  85. 	int countWays(long long n)
  86. 	{
  87. 		matrix a; a.take(mat);
  88. 		matrix b = pow(a,n*4);
  89. 		return b.a[0][0];
  90. 	}
  91. };
  92.  
  93.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
/usr/lib/gcc/i586-linux-gnu/4.9/../../../i386-linux-gnu/crt1.o: In function `_start':
(.text+0x18): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout 
Standard output is empty
https://ideone.com/T6HXhE
language:
C++ (gcc 8.3)
created:
9 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!