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

nis6then:But for

n = 6the answer is2.< deleted >

Well, what is "generic dp" in your opinion?

what is the correct formula ?? i dont think the recurrence is wrong but we have to define base conditions from 0 to 49 . @providec please provide the correct formula incase we are wrong . that d be of much help . thank you :)

please let me know the 50*50 matrix for which exponentiation is to be done

You can find solution in "Concrete Mathematics", chapter 7.