fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3. #define ull unsigned long long
  4.  
  5. struct matrix {
  6. 	int x11, x12, x21, x22;
  7.  
  8. 	matrix() {
  9. 		x11 = 1, x12 = 0, x21 = 0, x22 = 1;
  10. 	}
  11.  
  12. 	matrix(int a, int b, int c, int d) {
  13. 		x11 = a, x12 = b, x21 = c, x22 = d;
  14. 	}
  15.  
  16. 	matrix mul(matrix M) {
  17. 		int a, b, c, d;
  18. 		a = (x11*M.x11 + x12*M.x21) % 1000;
  19. 		b = (x11*M.x12 + x12*M.x22) % 1000;
  20. 		c = (x21*M.x11 + x22*M.x21) % 1000;
  21. 		d = (x21*M.x12 + x22*M.x22) % 1000;
  22. 		return matrix(a,b,c,d);
  23. 	}
  24.  
  25. 	void print() {
  26. 		cout << x11 << " " << x12 << endl << x21 << " " << x22 << endl;
  27. 	}
  28. };
  29.  
  30. matrix power(matrix A, ull n) {
  31. 	if (n == 0)
  32. 		return matrix();
  33. 	if (n == 1)
  34. 		return A;
  35. 	if (n % 2 == 0)
  36. 		return power(A.mul(A), n/2);
  37. 	if (n % 2 == 1)
  38. 		return A.mul(power(A.mul(A), n/2));
  39. }
  40.  
  41. int main() {
  42. 	ull n;
  43. 	int tmp, x, y;
  44. 	matrix A(1,1,1,0), B;
  45. 	while (cin >> n) {
  46. 		B = power(A,n-1);
  47. 		cout << (B.x21 + B.x22) % 1000 << endl;
  48. 	}
  49. 	return 0;
  50. }
Success #stdin #stdout 0s 3416KB
comments (?)
stdin
copy 
10
stdout
copy 
55
https://ideone.com/nGXGIx
language:
C++14 (gcc 8.3)
created:
9 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!