fork(9) download
copy 
  1. /*
  2. http://w...content-available-to-author-only...f.com/problems/GROWGOLD 
  3.  
  4. Golden Trees
  5. Problem code: GROWGOLD
  6.     
  7. SUBMITMY SUBMISSIONSALL SUBMISSIONS
  8. All submissions for this problem are available.
  9.  
  10. Long ago there was a beautiful kingdom in the island of Sona, the golden island, deep inside Africa. The trees in Sona island are made of gold and farmers are the richest group of people and are also heavy tax payers.
  11. As you know that price of gold increases every year, the minister of Sona has proposed the following tax policy.
  12. Pay initTax units of gold in the first year.
  13.  
  14. In each of the next slot1 years, pay one unit of gold more than the previous year.
  15.  
  16. In each of the next slot2 years, pay double the units of gold of the previous year.
  17.  
  18. In each of the following years, pay number of gold units equal to the product of the number of units paid in K recent years.
  19.  
  20.  
  21. Given an integer N, find the number of units of gold to be paid in the Nth year. This result can be huge, so output the result modulo 100000007 (108+7).
  22. Input
  23.  
  24. First line has an integer T (number of test cases, 1 = T = 3). Each of the next T lines has 5 integers, initTax slot1 slot2 K N.
  25. 1 = initTax, slot1, slot2 = 50
  26. 1 = K = slot1 + slot2 + 1
  27. 1 = N = 1000000000 (109)
  28. Output
  29.  
  30. For each test case, output the tax in units of gold to be paid in the Nth year modulo 100000007 (108+7).
  31. Example
  32.  
  33. Input:
  34. 3
  35. 1 3 2 4 4
  36. 1 3 2 4 7
  37. 1 3 2 4 9
  38.  
  39. Output:
  40. 4
  41. 1536
  42. 18811834
  43.  
  44. Explanation:
  45.  
  46. Let tax[i] be the tax paid in ith year.
  47.  
  48. Init : tax[1] = 1
  49.  
  50. Next 3 years in slot1 (tax[i] = tax[i-1] + 1) : tax[2] = 2 , tax[3] = 3, tax[4] = 4
  51.  
  52. Next 2 years in slot2 (tax[i] = 2 * tax[i-1]) : tax[5] = 8 , tax[6] = 16
  53.  
  54. We have tax[1..6] = { 1, 2, 3, 4, 8, 16 }
  55.  
  56. tax[7] = tax[3] * tax[4] * tax[5] * tax[6] = 3 * 4 * 8 * 16 = 1536
  57.  
  58. similarly, tax[9] = tax[5] * tax[6] * tax[7] * tax[8].
  59.  
  60. Do not forget to print only the reminder of the result when divided by 100000007 (108+7).
  61. */
  62. #include <iostream>
  63. #include <cassert>
  64. #include <cstdio>
  65. #include <algorithm>
  66. #include <utility>
  67. #include <string>
  68. #include <vector>
  69. #include <cmath>
  70. #include <set>
  71. #include <stack>
  72. #include <queue>
  73. #include <map>
  74. #include <sstream>
  75. #include <ctime>
  76. #include <numeric>
  77. #include <cstring>
  78. #include <functional>
  79. #define MOD 100000007
  80. using namespace std;
  81.  
  82. //Class Matrix
  83. class Matrix {
  84.     unsigned _row, _col;
  85.     string _name;
  86.     int** _mat;
  87. public:
  88. 	//default ctor
  89. 	Matrix():_row(0), _col(0),_name("UnInit"){}
  90. 	//cleans up any memory taken by _mat and allocates afresh as per row and col value.
  91. 	void init(unsigned rw, unsigned cl, const string& name="NoName"){
  92. 		//cout<<"DEBUG: In init. name="<<name<<endl;
  93. 		if(_row > 0){
  94. 			if(_col > 0){
  95. 				for(unsigned r=0; r<_row; r++)
  96. 					delete[] _mat[r];
  97. 			}
  98. 			delete[] _mat;
  99. 		}
  100. 		_name = name;
  101. 		_row = rw;
  102. 		_col = cl;
  103.         _mat = new int*[_row]; //TODO: use exception handling
  104.         for (unsigned r=0; r<_row; r++){
  105.             _mat[r] = new int[_col];
  106. 			for(unsigned c=0; c<_col; c++)
  107. 				_mat[r][c] = 0;
  108. 		}
  109.     }
  110. 	//copy ctor
  111.     Matrix(const Matrix& mat){
  112. 		_row = 0; _col = 0; _name = "UnInit";
  113. 		init(mat._row, mat._col, "CreatedInCopyCtor");
  114.         for (unsigned i=0; i<mat._row; i++)
  115.             for (unsigned j=0; j<mat._col; j++)
  116.                 _mat[i][j] = mat._mat[i][j];
  117.     }
  118.     void operator=(const Matrix& mat){
  119. 		init(mat._row, mat._col, "Copy of "+mat._name);
  120.         for (unsigned i=0; i<mat._row; i++)
  121.             for (unsigned j=0; j<mat._col; j++)
  122.                 _mat[i][j] = mat._mat[i][j];
  123.     }
  124. 	//Creates and returms mat^expo in LOG(expo) time. :)
  125. 	static Matrix* power(const Matrix& mat, unsigned expo, const int modulus) {
  126.         //cout<<"DEBUG: Entered power\n";
  127.         vector<Matrix*> cache;//eg. cache[0] = (mat)^1, cache[3] = (mat)^8
  128.         Matrix* ansMat = new Matrix();
  129.         ansMat->operator=(mat);
  130. 		expo--;//as ansMat already is assigned as mat
  131. 		Matrix* cacheMat = new Matrix(); cacheMat->operator=(mat);
  132.         cache.push_back(cacheMat);
  133.         //cout<<"DEBUG: cache.pushed()\n";
  134.         //find max 2 ki power needed for finding ansMat. let it be 'count'. Ex. for expo=31 (11111), 'count' is 4.
  135.         unsigned count = 0;
  136. 		int expoTmp = expo>>1;
  137. 		while(expoTmp){
  138. 			count++;
  139. 			expoTmp>>=1;
  140. 		}
  141.         //cout<<"DEBUG:count = "<<count<<endl;
  142.         for (unsigned i=1; i<=count; i++) {
  143.             Matrix* tmpMat = new Matrix();
  144. 			tmpMat->operator=(*cache[i-1]);
  145. 			tmpMat->operator=(*(tmpMat->multiply(cache[i-1], modulus)));
  146.             cache.push_back(tmpMat);
  147.             //cout<<"DEBUG: cache["<<cache.size()-1<<"] created as follows:"; tmpMat->print(cout);
  148.         }
  149.         for (unsigned bit=0; bit<=count; bit++)
  150.             if (1<<bit & expo) {
  151.                 //cout<<"DEBUG:bit "<<bit<<" is set.\n";
  152. 				//cout<<"DEBUG: Will call multiply with following mats:"; ansMat->print(cout); cache[bit]->print(cout);
  153. 				Matrix* tmpMat = ansMat->multiply(cache[bit], modulus);
  154.                 //cout<<"DEBUG:tmpMat create for bit "<<bit<<" as follows:"; tmpMat->print(cout);
  155.                 ansMat->operator=(*tmpMat);
  156.                 //cout<<"DEBUG:ansMat *= tmpMat DONE for bit="<<bit<<" with result:."; ansMat->print(cout);
  157.             }
  158. 		for(unsigned i=0; i<cache.size(); i++)
  159. 			delete cache[i];
  160.         return ansMat;
  161.     }
  162.     Matrix* multiply(const Matrix* mat, const int modulus) {
  163.         assert(this->_col == mat->_row);
  164. 		assert(mat != NULL);
  165.         Matrix* ans = new Matrix();
  166. 		ans->init(this->_row, mat->_col, "CreatedInMultiply");
  167.         for (unsigned row=0; row<this->_row; row++)
  168.             for (unsigned col=0; col<mat->_col; col++) {
  169.                 ans->_mat[row][col] = 0;
  170. 				//cout<<"DEBUG: In multiply, ans->_mat["<<row<<"]["<<col<<"] computed as \n";
  171.                 for (unsigned index=0; index<this->_col; index++){
  172. 					//cout<<"DEBUG:\t"<<this->_mat[row][index]<<"*"<<mat->_mat[index][col]<<endl;
  173.                     long long tmp = ans->_mat[row][col];
  174. 					tmp += this->_mat[row][index]*(long long)(mat->_mat[index][col]);
  175. 					if(tmp >= modulus)
  176. 						ans->_mat[row][col] = tmp%modulus;
  177. 					else 
  178. 						ans->_mat[row][col] = tmp;
  179. 				}
  180. 				//cout<<"DEBUG:\t"<<ans->_mat[row][col]<<endl;
  181.             }
  182.         return ans;
  183.     }	
  184.     void setColumn(unsigned colIndex, int value) {
  185.         for (unsigned i=0; i<_row; i++)
  186.             _mat[i][colIndex] = value;
  187.     }
  188.     int& getElement(unsigned rowIndex/*1 based*/, unsigned colIndex/*1 based*/) {
  189.         assert(rowIndex<_row);
  190.         assert(colIndex<_col);
  191.         return _mat[rowIndex][colIndex];
  192.     }
  193.     void print(ostream& cout) {
  194.         cout<<endl;
  195.         for (unsigned r=0; r<_row; r++) {
  196.             for (unsigned c=0; c<_col; c++)
  197.                 cout<<_mat[r][c]<<"\t";
  198.             cout<<endl;
  199.         }
  200.         cout<<endl;
  201. 	}
  202.     ~Matrix() {
  203.         //cout<<"DEBUG: In dtor for "<<this->_name<<endl;
  204.         for (unsigned r=0; r<_row; r++)
  205.             delete[] _mat[r];
  206.         delete[] _mat;
  207.     }
  208. };
  209.  
  210.  
  211. long long myPowMOD(const int num, const int expo){
  212.     Matrix mat;
  213. 	mat.init(1, 1, "CreatedInMain");//inits all elems with 0;
  214.     mat.getElement(0,0) = num;
  215.     //cout<<"DEBUG:power("<<num<<", 1):";    mat.print(cout);
  216.  
  217.     Matrix* mat2 = Matrix::power(mat, expo, MOD);
  218.     //cout<<"DEBUG:power("<<num<<", "<<expo<<"):";    mat2->print(cout);
  219.  
  220. 	long long ans = mat2->getElement(0,0);
  221. 	delete mat2;
  222. 	return ans;
  223. }
  224. int findLastYearTax(unsigned expo, const vector<int>& list){
  225.     const unsigned size = list.size();
  226.     Matrix mat;
  227. 	mat.init(size, size, "CreatedInMain");//inits all elems with 0;
  228.     mat.setColumn(0, 1);//sets column 0 as 1
  229.     for (unsigned colIndex=1; colIndex<size; colIndex++)
  230.         mat.getElement(colIndex-1,colIndex) = 1;
  231.     //cout<<"DEBUG:power(mat, 1):";    mat.print(cout);
  232.  
  233.     Matrix* ansMat = Matrix::power(mat, expo, MOD-1);
  234.     //cout<<"DEBUG:power(mat, "<<expo<<"):";    ansMat->print(cout);
  235.  
  236. 	long long ans = 1;
  237. 	for(unsigned index=0; index<size; index++){
  238. 		ans *= myPowMOD(list[size-1-index], ansMat->getElement(index,0));
  239. 		if(ans>=MOD)
  240. 			ans %= MOD;
  241. 	}
  242. 	delete ansMat;
  243. 	return ans;
  244. }
  245. void solve()
  246. {
  247. 	int initTax, s1, s2, k, n;
  248. 	cin>>initTax>>s1>>s2>>k>>n;
  249. 	int ans = initTax;
  250. 	if(n < 1+s1+s2+1){
  251. 		if(n<=s1+1)
  252. 			ans += n-1;
  253. 		else{
  254. 			ans += s1;
  255. 			n-= (s1+1);
  256. 			while(n--)
  257. 			{
  258. 				ans<<=1;
  259. 				ans = (ans>=MOD)?(ans%MOD):ans;
  260. 			}
  261. 		}
  262. 	}else{//maintain list of amount of tax paid in last k years.
  263. 		assert(k<=1+s1+s2);
  264. 		vector<int> list;
  265. 		if(k == 1+s1+s2){
  266. 			list.push_back(initTax);
  267. 			for(int i=1; i<=s1; i++)
  268. 				list.push_back(initTax+i);
  269. 		}else if(k>s2){
  270. 			for(int i=k-s2; i<=s1; i++)
  271. 				list.push_back(initTax+i);
  272. 		}
  273. 		int prevTax = initTax + s1;
  274. 		for(int years=1; years<=s2; years++){
  275. 			int curTax = prevTax<<1;
  276. 			curTax = ((curTax>=MOD)?(curTax%MOD):(curTax));
  277. 			if(s2-years+1 <= k)
  278. 				list.push_back(curTax);
  279. 			prevTax = curTax;
  280. 		}
  281.  
  282. 		//cout<<"DEBUG:list's k elements: "; for(unsigned i=0; i<list.size(); i++) cout<<list[i]<<"\t"; cout<<endl;
  283. 		int yearsLeft = n-1-s1-s2;
  284. 		ans = findLastYearTax(yearsLeft, list);//list[size()-1] has late year tax value
  285. 	}
  286. 	//cout<<"DEBUG: ANS=";
  287. 	cout<<ans<<endl;
  288. }
  289. int main(){
  290. 	int tt;
  291. 	cin>>tt;
  292. 	for(int t=0; t<tt; t++)
  293. 	{
  294. 		solve();
  295. 	}
  296. 	return 0;
  297. }
  298.  
Success #stdin #stdout 0s 3044KB
comments (?)
stdin
copy 
5
1 3 2 4 9
1 3 2 4 10
1 3 2 4 11
1 3 2 4 12
1 3 2 4 13
stdout
copy 
18811834
84208956
35889352
75453662
44609468
https://ideone.com/scwT0S
language:
C++ (gcc 8.3)
created:
11 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!