fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5.  
  6.  
  7. ll k, mod;
  8. vector<ll>b;
  9. vector<ll>c;
  10.  
  11. vector<vector<ll>> multiply(vector<vector<ll>>A,vector<vector<ll>>B)
  12. {
  13. 	vector<vector<ll>> ans(k+2, vector<ll>(k+2));
  14. 	for(int i=1; i<=k+1; i++)
  15. 	{
  16. 		for(int j=1; j<=k+1; j++)
  17. 		{
  18. 			ll fin = 0;
  19. 			for(int ff=1; ff<=k+1; ff++)
  20. 				fin = (  fin+ ((A[i][ff]*B[ff][j])%mod) )%mod;
  21. 			ans[i][j] = fin;
  22. 		}
  23. 	}
  24. 	return ans;
  25. }
  26.  
  27.  
  28. vector<vector<ll>> pow(vector<vector<ll>>T, ll n)
  29. {
  30. 	if(n==1) return T;
  31.  
  32. 	if(n&1)
  33. 		return multiply(T,pow(T,n-1));
  34. 	else
  35. 	{
  36. 		vector<vector<ll>> X = pow(T, n/2);
  37. 		return multiply(X, X);
  38. 	}
  39. }
  40.  
  41.  
  42. ll compute(ll n)
  43. {
  44.  
  45. 	if(n<=0)	return -1;
  46.  
  47. 	if(n<=k)
  48. 	{
  49. 		ll finsum = 0;
  50. 		for(int i=1; i<=n; i++)
  51. 			finsum = (finsum+b[i-1])%mod;
  52. 		return finsum;
  53. 	}
  54.  
  55. 	vector<ll>F(k+2);
  56.  
  57. 	F[1] = 0;
  58. 	for(int i=0; i<k; i++)
  59. 		F[i+2] = b[i];
  60.  
  61. 	// for(int i=1; i<=k+1; i++)
  62. 	// 	cout<<F[i]<<endl;
  63. 	// cout<<"***"<<endl;
  64.  
  65. 	vector<vector<ll>>T(k+2, vector<ll>(k+2, 0));
  66.  
  67. 	T[1][1] = 1;
  68. 	T[1][2] = 1;
  69.  
  70. 	for(int i=2; i<=k; i++)
  71. 	{
  72. 		for(int j=1; j<=k+1; j++)
  73. 		{
  74. 			if(i==j-1)
  75. 				T[i][j] = 1;
  76. 		}
  77. 	}
  78.  
  79.  
  80.  
  81. 	for(int i=1; i<=k; i++)
  82. 		T[k+1][i+1] = c[k-i];
  83.  
  84. 	// for(int i=1; i<=k+1; i++)
  85. 	// {
  86. 	// 	for(int j=1; j<=k+1; j++)
  87. 	// 		cout<<T[i][j]<<" ";
  88. 	// 	cout<<endl;
  89. 	// }
  90. 	// cout<<"***"<<endl;
  91.  
  92. 	T = pow(T, n);
  93.  
  94. 	// for(int i=1; i<=k+1; i++)
  95. 	// {
  96. 	// 	for(int j=1; j<=k+1; j++)
  97. 	// 		cout<<T[i][j]<<" ";
  98. 	// 	cout<<endl;
  99. 	// }
  100. 	// cout<<"***"<<endl;
  101.  
  102. 	ll finans = 0;
  103. 	for(int i=1; i<=k+1; i++)
  104. 		finans = ( finans + ((T[1][i]*F[i])%mod) )%mod;
  105.  
  106. 	return finans;
  107.  
  108. }
  109.  
  110.  
  111. int main()
  112. {
  113.  
  114. 	ios::sync_with_stdio(0);   
  115.     cin.tie(0);
  116.     #ifndef ONLINE_JUDGE   
  117.     freopen("input.txt", "r", stdin);   
  118.     freopen("output.txt", "w", stdout);   
  119.     #endif
  120.  
  121. 	ll t, val, n, m;
  122. 	cin>>t;
  123. 	while(t--)
  124. 	{
  125.  
  126. 		cin>>k;
  127. 		b.clear();
  128. 		c.clear();
  129. 		b.reserve(k);
  130. 		c.reserve(k);
  131.  
  132. 		for(int i=0; i<k; i++)
  133. 		{
  134. 			cin>>val;
  135. 			b.push_back(val);
  136. 		}
  137.  
  138. 		for(int i=0; i<k; i++)
  139. 		{
  140. 			cin>>val;
  141. 			c.push_back(val);
  142. 		}
  143.  
  144. 		cin>>m;
  145. 		cin>>n;
  146. 		cin>>mod;
  147.  
  148. 		ll aa = compute(m-1);
  149. 		ll bb = compute(n);
  150. 		// cout<<bb<<" "<<aa<<endl;
  151. 		ll finans = (bb-aa+mod)%mod;
  152. 		cout<<finans<<endl;
  153.  
  154. 	}
  155.  
  156. 	return 0;
  157. }
Success #stdin #stdout 0s 4536KB
comments (?)
stdin 
1
2
1 1
1 1
2 10 1000003
stdout 
142
https://ideone.com/8fX9lb
problem SPP, based on SPOJ submission 25599530 (CPP14), 2020-03-22 10:47:30
language:
C++14 (gcc 8.3)
created:
5 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!