fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. ll b[12],c[12];
  6. int k;
  7.  
  8. ll solve(ll n);
  9. ll** form_trans_matrix();
  10. ll** power(ll **trans,int exp);
  11. //void print(ll **a,int m,int n);
  12. ll** multiply(ll **a,ll **b);
  13.  
  14. int main(){
  15. 	int t;cin>>t;
  16. 	ll n;
  17. 	int i;
  18. 	while(t--)
  19. 	{
  20. 		cin>>k;
  21. 		for(i=0;i<k;i++)
  22. 			cin>>b[i];
  23. 		for(i=0;i<k;i++)
  24. 			cin>>c[i];
  25. 		cin>>n;
  26. 		cout<<solve(n)<<endl;
  27. 	}
  28. }
  29.  
  30. ll solve(ll n)
  31. {
  32. 	if(n<=k)
  33. 		return b[n-1]%1000000000;
  34. 	ll **trans = form_trans_matrix();
  35. 	trans = power(trans,n-k);
  36. 	ll ans=0;
  37. 	for(int i=0;i<k;i++)
  38. 	{
  39. 		ans+= trans[k-1][i] * b[i];
  40. 		ans = ans % 1000000000;
  41. 	}
  42.  
  43. 	//delete the matrix
  44. 	 for(int i = 0; i < k; ++i) {
  45.         delete[] trans[i];   
  46.     }
  47.     delete[] trans;
  48.  
  49. 	return ans;
  50. }
  51. //exponentiation 
  52. ll** power(ll **trans,int exp){
  53. 	if(exp==1)
  54. 		{
  55. 		ll **mul =  new ll*[k];
  56. 			for(int i=0;i<k;i++)
  57. 				mul[i] = new ll[k];
  58. 		for(int i=0;i<k;i++)
  59. 			for(int j=0;j<k;j++)
  60. 				mul[i][j] = trans[i][j];
  61. 			return mul;
  62. 		}
  63. 	ll** res = power(trans,exp/2);
  64. 	multiply(res,res);
  65.  
  66. 	if(exp&1)
  67. 		multiply(res,trans);
  68.  
  69. //	print(res,k,k);
  70. 	return res;
  71. }
  72. //multiplies two matrices and stores the result in matrix a
  73. ll** multiply(ll **a,ll **b){
  74.  
  75. 	ll **mul =  new ll*[k];
  76. 		for(int i=0;i<k;i++)
  77. 			mul[i] = new ll[k];
  78. 	    for (int i = 0; i < k; i++) 
  79.     	    for (int j = 0; j < k; j++) 
  80.         	{ 
  81.             	mul[i][j] = 0; 
  82.             	for (int z = 0; z < k; z++) 
  83.                 	mul[i][j] += ( a[i][z]*b[z][j] )%1000000000; 
  84.         	}   
  85.     	for (int i=0; i<k; i++) 
  86.         	for (int j=0; j<k; j++) 
  87.             	a[i][j] = mul[i][j]; 
  88. } 
  89.  
  90.  
  91. //base matrix for exponentiation
  92. ll** form_trans_matrix(){
  93. 	ll **trans =  new ll*[k];
  94. 	for(int i=0;i<k;i++)
  95. 		trans[i] = new ll[k];
  96. 	//transformation matrix formation
  97. 	for(int i=0;i<k-1;i++)
  98. 		for(int j=0;j<k;j++)
  99. 		{
  100. 			if(j ==(i+1) )
  101. 				trans[i][j]=1;
  102. 			else
  103. 				trans[i][j]=0;
  104. 		}
  105. 	for(int i=0;i<k;i++)
  106. 		trans[k-1][i] = c[k-i-1];
  107. 	return trans;
  108. }
  109. /*
  110. void print(ll **a,int m,int n){
  111. 		cout<<endl;
  112. 		int i,j;
  113. 		for(int i=0;i<m;i++)
  114. 			{
  115. 				for(int j=0;j<n;j++)
  116. 					cout<<a[i][j]<<"\t";
  117. 				cout<<endl;
  118. 				}
  119. 	}
  120. */
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
1 2 1 1 1 1 7
stdout
copy 
13
https://ideone.com/A79Nik
language:
C++14 (gcc 8.3)
created:
6 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!