OJ Board

I tried DP but got TLE.
what could a better algorithm for this problem?
please help.
the complexity of my algorithm for each query is O( 4 * v + 4 * v ) .

I think there needs something like Generating Function, but I don't know how.

Hmm... I don't know either... The only thing I am pretty sure about is that
DP probably won't pass no matter how hard you try.

I thought about generating function, but I don't see how to compute it fast enough.

For example, we have 3 $1, 2 $2, 3 $5 and 1 $10, then we can represent it as the polynomial (1+x+x^2+x^3)*(1+x^2+x^4)*(1+x^5+x^10+x^15)*(1+x^10). And the coefficient of x^d in the expanded form is the number of ways to make $d .

Well, the idea is to represent the polynomial as a difference of 2 infinite series. The dp solution will be able to find the coefficient for an infinite series easily.

Inclusion-exclusion finishes off the problem.

A little hint: You should be able to answer each query in O(2^W) based on the result of a DP, where W is the number of coins, which is always 4 in this problem.

i.e. After running a DP, you should answer each query in almost constant time.

Cho wrote:A little hint: You should be able to answer each query in O(2^W) based on the result of a DP, where W is the number of coins, which is always 4 in this problem.

i.e. After running a DP, you should answer each query in almost constant time.

I still can't understand. Could you please explain in more details?

Use principle of inclusion-exclusion to answer queries.

mf wrote:Use principle of inclusion-exclusion to answer queries.

er... Is it something like this :

If we call 4 kinds of coins A, B, C and D. Then for each query, we calcuate (the number of ways using A) + (the number of ways using B) + (the number of ways using C) + (the number of ways using D) - (the number of ways using A and B) - (the number of ways using A and C) - ... + (the number of ways using A and B and C) + ... - (the number of ways using A and B and C and D)

But how to find these (the number of ways using A and B), (the number of ways using B and C and D)...?

For two coins it's something like this:

Let N be the total number of ways of obtaining value v using the given coin denominations,
let N1 and N2 be the number of ways, in which the first or second coin is used more than d[1] or d[2] times, respectively,
let N12 be the number of ways in which the first coin is used more than d[1] times, and the second coin is used more than d[2] times.
Then the number of ways in which no coin is used more times than necessary is: N - N1 - N2 + N12.

How to compute these N's:
N1 = number of ways in which the first coin is used more than d[1] times, by definition. So, use the first coin d[1]+1 times, and find the number of ways to obtain the remaining value.

Got it. Thanks very much!

I get too many WR.
Sample I/O plz.........

Thanks
keep posting.

Sapnil.

Did you use long long int?

It's necessary for solving it.

Thanks chen,I don't think about this case.........
But there are some mistake in my code.

Thanks
keep posting.

Sapnil.