fork download
copy 
  1. #include <iostream>
  2.  
  3. static constexpr auto MOD = 1000000007LL;
  4.  
  5. inline /*hint hint*/ long long mod(long long x)
  6. {
  7.     if (x >= 0 && x < MOD) return x;
  8.  
  9.     x %= MOD;
  10.     if (x < 0)
  11.         return x + MOD;
  12.  
  13.     return x;
  14. }
  15.  
  16. struct matrix
  17. {
  18. 	long long m[4][4];
  19.  
  20. 	static matrix multiply(const matrix &a, const matrix &b)
  21. 	{
  22. 		matrix c;
  23.  
  24. 		for (int i = 0; i < 4; i++)
  25. 			for (int j = 0; j < 4; j++)
  26. 			{
  27. 				c.m[i][j] = 0;
  28. 				for (int k = 0; k < 4; k++)
  29. 					c.m[i][j] += a.m[i][k] * b.m[k][j];
  30. 			}
  31.  
  32. 		return c;
  33. 	}
  34.  
  35. 	void normalize()
  36. 	{
  37. 		for (int i = 0; i < 4; i++)
  38. 			for (int j = 0; j < 4; j++)
  39. 				m[i][j] = mod(m[i][j]);
  40. 	}
  41. };
  42.  
  43. static matrix operator*(matrix const& a, matrix const& b)
  44. {
  45. 	return matrix::multiply(a,b);
  46. }
  47.  
  48. template <typename T>
  49. T pow(T const&a, long long n)
  50. {
  51.     if (n == 0) throw "not implemented";
  52.     if (n == 1) return a;
  53.  
  54.     auto b = pow(a*a, n>>1);
  55.  
  56. 	return (n & 1)? b*a : b;
  57. }
  58.  
  59. int main()
  60. {
  61. 	//std::cout << "pow(2,  0): " << pow(2,  0) << std::endl;
  62. 	std::cout << "pow(2,  1): " << pow(2ll,  1) << std::endl;
  63. 	std::cout << "pow(2,  2): " << pow(2ll,  2) << std::endl;
  64. 	std::cout << "pow(2,  3): " << pow(2ll,  3) << std::endl;
  65. 	std::cout << "pow(2,  4): " << pow(2ll,  4) << std::endl;
  66. 	std::cout << "pow(2,  5): " << pow(2ll,  5) << std::endl;
  67. 	std::cout << "pow(2, 10): " << pow(2ll, 10) << std::endl;
  68. 	std::cout << "pow(2, 16): " << pow(2ll, 16) << std::endl;
  69. 	std::cout << "pow(2, 32): " << pow(2ll, 32) << std::endl;
  70.  
  71. 	matrix v = { { { 1,2,3,4}, { 2,3,4,5},
  72. 		           { 3,4,5,6}, { 7,8,9,0} } };
  73.  
  74. 	for (long i = 0; i< (1ul << 22ul); ++i)
  75. 	{
  76. 		auto e = pow(v, 16);
  77. 		e.normalize();
  78. 	}
  79. }
  80.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9MmE9
language:
C++14 (gcc 8.3)
created:
13 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!