Hi,
I was trying to solve this problem of finding no of possible ways of changing a value n.
http://www.spoj.com/problems/TPC07/
TJU judge link:
http://acm.tju.edu.cn/toj/showp2817.html
now this problem has a constraint of n<=10^9.so,I can't declare an array of that size and run a dp approach.Also,I think this problem will require BigInteger support by seeing the answer for the second test case.
So,any help on how to solve it using C/C++ would be much appreciated.
In DP, we must use this formula: F(i) = F(i-1) + F(i-5) + F(i-10) + F(i-25) + F(i-50)
As you can see, it is a linear function, so we can find F(n) faster than O(N) using matrix multiplications.
You can google "Fast k-th fibonacci algorithm", it can help you understand how to find F(N) for any linear function in O(logN*k^3).
But,in order to solve it in C/C++ I need to use some BigInteger library right??and also,I can't preprocess it.So,for every test case,I have to calculate this??
I think it is better for you to write Long Arithmetics yourself, without any extra libraries. You need to write only addition operation.
Ok thanx for clarifying that part. Now,I can't store f[1],f[2],..,f[n] because n can go upto 10^9.So what is the solution to that problem? For a particular n,should I find each of f(n-1),f(n-5),.. by matrix exponentiation??Will that pass in time limit?
I think it will pass time limit. And please, read about finding f(n) for linear function using matrix exponentiation and everything will be clear.
And yes, formula is wrong. It counts "take 1 penny and 2 nickel" and "take 2 nickel and 1 penny" as different ways. But I think it can be fixed with small correction.
Your formula is wrong. For instance if n is 6 then:
But for n = 6 the answer is 2.
< deleted >
Well, what is "generic dp" in your opinion?
You can find solution in "Concrete Mathematics", chapter 7.