fork download
copy 
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <cmath>
  4. #define MOD 1000000007
  5. using namespace std;
  6.  
  7. struct Matrix
  8. {
  9. 		long long int A[2][2] ;
  10.  
  11. };
  12.  
  13. Matrix mult(Matrix M, Matrix N){
  14.  
  15.  
  16. 	Matrix C 	;
  17.  
  18. 	C.A[0][0] = (M.A[0][0] * N.A[0][0] + M.A[0][1] * N.A[1][0])	% (MOD - 1)   ;           
  19. 	C.A[0][1] = (M.A[0][0] * N.A[0][1] + M.A[0][1] * N.A[1][1]) % (MOD - 1)   ;
  20. 	C.A[1][0] = (M.A[1][0] * N.A[0][0] + M.A[1][1] * N.A[1][0]) % (MOD - 1)   ;  
  21. 	C.A[1][1] = (M.A[1][0] * N.A[0][1] + M.A[1][1] * N.A[1][1]) % (MOD - 1)   ;
  22.  
  23. 	return C;
  24.  
  25. }
  26.  
  27. Matrix Bin_Exp(Matrix A, int n)	{
  28.  
  29. 	if (n == 1)
  30. 		return A	;
  31.  
  32. 	Matrix inter = Bin_Exp(A, n / 2)	;
  33.  
  34. 	if (n % 2)
  35. 		return mult(A, mult(inter, inter));
  36. 	return mult(inter, inter)	;
  37. }
  38.  
  39. long long int bin_exp(long long int base, long long int exp){
  40.  
  41. 	if (exp == 0)
  42. 		return 1;
  43.  
  44. 	if (exp == 1)
  45. 		return base % MOD	;
  46.  
  47. 	long long int inter = bin_exp(base, exp / 2)	;
  48. 	if (exp % 2)
  49. 		return ((base % MOD)  * (inter * inter)%MOD)%MOD;
  50. 	return (inter * inter) % MOD;
  51.  
  52. }
  53.  
  54.  
  55. int main(){
  56.  
  57. 	int t, F0, F1, n, K ;
  58. 	Matrix trans ;
  59. 	scanf("%d", &t)	;
  60. 	while(t--){
  61.  
  62. 		scanf("%d %d %d %d", &F0, &F1, &n, &K);
  63.  
  64. 		trans.A[0][0] = K; trans.A[0][1] = K ;
  65. 		trans.A[1][0] = 1; trans.A[1][1] = 0 ;
  66.  
  67. 		if (n == 1){
  68. 			printf("%d\n", F1);
  69. 			continue;
  70. 		}
  71.  
  72. 		if (n == 0){
  73. 			printf("%d\n", F0);
  74. 			continue;
  75. 		}
  76.  
  77. 		Matrix ans = Bin_Exp(trans, n-1)	; 
  78.  
  79. 		long long int sol = (bin_exp(F1, ans.A[0][0]) * bin_exp(F0, ans.A[0][1]))%MOD	;
  80. 		printf("%lld\n", sol);
  81. 	}
  82.  
  83. 	return 0	;
  84. }
  85.  
  86.  
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
1
1 1 2 1
stdout
copy 
1
https://ideone.com/sPPc4a
language:
C++14 (gcc 8.3)
created:
7 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!