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. 		int i, j, k;
  23. 		matrix c;
  24.  
  25. 		for (i = 0; i < 4; i++)
  26. 			for (j = 0; j < 4; j++)
  27. 			{
  28. 				c.m[i][j] = 0;
  29. 				for (k = 0; k < 4; k++)
  30. 					c.m[i][j] += a.m[i][k] * b.m[k][j];
  31. 				c.m[i][j] = mod(c.m[i][j]);
  32. 			}
  33.  
  34. 		return c;
  35. 	}
  36. };
  37.  
  38. static matrix operator*(matrix const& a, matrix const& b)
  39. {
  40. 	return matrix::multiply(a,b);
  41. }
  42.  
  43. template <typename T>
  44. T pow(T const&a, long long n)
  45. {
  46.     if (n == 0) throw "not implemented";
  47.     if (n == 1) return a;
  48.  
  49.     auto b = pow(a*a, n>>1);
  50.  
  51.     return (n & 1)? b*a : b;
  52. }
  53.  
  54. int main()
  55. {
  56. 	//std::cout << "pow(2,  0): " << pow(2,  0) << std::endl;
  57. 	std::cout << "pow(2,  1): " << pow(2ll,  1) << std::endl;
  58. 	std::cout << "pow(2,  2): " << pow(2ll,  2) << std::endl;
  59. 	std::cout << "pow(2,  3): " << pow(2ll,  3) << std::endl;
  60. 	std::cout << "pow(2,  4): " << pow(2ll,  4) << std::endl;
  61. 	std::cout << "pow(2,  5): " << pow(2ll,  5) << std::endl;
  62. 	std::cout << "pow(2, 10): " << pow(2ll, 10) << std::endl;
  63. 	std::cout << "pow(2, 16): " << pow(2ll, 16) << std::endl;
  64. 	std::cout << "pow(2, 32): " << pow(2ll, 32) << std::endl;
  65.  
  66. 	matrix v = { { { 1,2,3,4}, { 2,3,4,5},
  67. 		           { 3,4,5,6}, { 7,8,9,0} } };
  68.  
  69. 	for (long i = 0; i< (1ul << 22ul); ++i)
  70. 		pow(v, 16);
  71. }
  72.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/c45oC
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!