fork(1) 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   ;           
  19. 	C.A[0][1] = (M.A[0][0] * N.A[0][1] + M.A[0][1] * N.A[1][1]) % MOD	;
  20. 	C.A[1][0] = (M.A[1][0] * N.A[0][0] + M.A[1][1] * N.A[1][0]) % MOD	;  
  21. 	C.A[1][1] = (M.A[1][0] * N.A[0][1] + M.A[1][1] * N.A[1][1]) % MOD	;
  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. 	if (exp == 1)
  44. 		return base	;
  45.  
  46. 	long long int inter = bin_exp(base, exp / 2)	;
  47. 	if (exp % 2)
  48. 		return (base % MOD  * (inter * inter) % MOD)%MOD;
  49. 	return (inter * inter) % MOD;
  50.  
  51. }
  52.  
  53.  
  54. int main(){
  55.  
  56. 	int t, F0, F1, n, K ;
  57. 	Matrix trans ;
  58. 	scanf("%d", &t)	;
  59. 	while(t--){
  60.  
  61. 		scanf("%d %d %d %d", &F0, &F1, &n, &K);
  62.  
  63. 		trans.A[0][0] = K; trans.A[0][1] = K ;
  64. 		trans.A[1][0] = 1; trans.A[1][1] = 0 ;
  65.  
  66. 		if (n == 1){
  67. 			printf("%d\n", F1);
  68. 			continue;
  69. 		}
  70.  
  71. 		if (n == 0){
  72. 			printf("%d\n", F0);
  73. 			continue;
  74. 		}
  75.  
  76. 		Matrix ans = Bin_Exp(trans, n-1)	; 
  77.  
  78. 		int sol = (bin_exp(F1, ans.A[0][0]) % MOD * bin_exp(F0, ans.A[0][1])%MOD)%MOD	;
  79. 		printf("%d\n", sol);
  80. 	}
  81.  
  82. 	return 0	;
  83. }
  84.  
  85.  
Success #stdin #stdout 0s 3476KB
comments ()
stdin
copy 
1
1 1 2 1
stdout
copy 
1
https://ideone.com/m19TN6
language:
C++14 (gcc 8.3)
created:
8 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!