fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std ;
  3.  
  4. #define MAXN 5 
  5. #define LL long long 
  6. #define sc(x) scanf("%d",&x) 
  7. #define pr(x) printf("%d\n",x) 
  8. #define MOD 1000000007
  9.  
  10.  
  11. int res[MAXN][MAXN],Temp[MAXN][MAXN],A[MAXN][MAXN],F[MAXN] , T , N ;
  12.  
  13.  
  14.  
  15. void init(){
  16. 	memset(res,0,sizeof res) ;
  17. 	memset(A,0,sizeof A) ;
  18. 	for(int i=0;i<MAXN;i++)
  19. 		res[i][i] = 1 ;
  20. 	A[0][1] = A[1][2] = A[2][3] = A[4][4] = 1 ;
  21. }
  22.  
  23.  
  24. void mult(int A[MAXN][MAXN],int B[MAXN][MAXN]){
  25.  
  26. 	for(int i=0;i<MAXN;i++){
  27. 		for(int j=0;j<MAXN;j++){
  28. 			Temp[i][j] = 0 ;
  29. 			for(int k=0;k<MAXN;k++){
  30. 				Temp[i][j] += (1LL * A[i][k] * B[k][j]) % MOD ;
  31. 				Temp[i][j] %= MOD ; 
  32. 			}
  33. 		}
  34. 	}
  35. 	for(int i=0;i<MAXN;i++){
  36. 		for(int j=0;j<MAXN;j++){
  37. 			A[i][j] = Temp[i][j] ;
  38. 		}
  39. 	}
  40. }
  41.  
  42. void power(int N){
  43.  
  44. 	while(N){
  45. 		if(N&1){
  46. 			mult(res,A) ;
  47. 		}
  48. 		N /= 2 ;
  49. 		mult(A,A) ;
  50. 	}
  51. }
  52. int main(){
  53.  
  54. 	sc(T) ;
  55. 	while(T--){
  56. 		sc(N) ;		
  57. 		init() ;
  58. 		for(int i=0;i<MAXN;i++){
  59. 			sc(A[3][i]) ;
  60. 			A[3][i] += MOD ;
  61. 			A[3][i] %= MOD ;
  62. 		}
  63. 		for(int i=0;i<MAXN-1;i++){
  64. 			sc(F[i]) ;
  65. 			F[i] += MOD ;
  66. 			F[i] %= MOD ;
  67. 		}
  68. 		F[4] = 1 ;
  69. 		power(N-1) ;
  70. 		int ans = 0 ;
  71. 		for(int i=0;i<MAXN;i++){
  72. 			ans += (1LL * F[i] * res[0][i]) % MOD ;
  73. 			ans %= MOD ;
  74. 		}
  75. 		pr(ans) ;
  76. 	}
  77. 	return 0 ; 
  78. }
  79.  
Success #stdin #stdout 0s 3144KB
comments (?)
stdin
copy 
1
5
1 1 1 1 1 1 1 1 1
stdout
copy 
5
https://ideone.com/nJnstg
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!