OJ Board

Hi,

I've read that there's a closed formula for this problem.. and it shouldn't be too hard since there're many people solved it during the contest..

So.. any hint about the formula? I've thought about this problem for few days but no results..

For me, it seems that this problem is more difficult than calculating n-th harmonic number and calculating n!, of which to the best of my knowledge, there's no closed formula...

Thanks.

First, you can separate i and j: sum_{i=1..n} sum_{j=1..m} (f(i)*g(j)) = (sum_{i=1..n} f(i)) * (sum_{j=1..m} g(j))

Then try to rewrite 1/(k(k+1)(k+2)(k+3)) as a linear combination of 1/k, 1/(k+1), 1/(k+2), 1/(k+3), and you'll get telescoping sums.

Well, the formula for 1/(k(k+1)) should've been standard knowledge and this problem is just an extension.
I think it has to be of the following forms:
A + 1/(B(n+1)(n+2)...(n+k)) where k+1 is the number of factors in the denominator of the summand.

The problem here is getting tle for no obvious reason. I had to make weird optimizations to get AC in more than 9.3 secs.

OK, thx, I think I got it

The keyword is telescoping.. hehe.. my math is poor..

sclo wrote: The problem here is getting tle for no obvious reason. I had to make weird optimizations to get AC in more than 9.3 secs.

I am not sure if it is your gcd/division implementation, or maybe the way you are multiplying it. My sum for [1,n] is something like A/(C1*(A+C2)), where A=f(n) and C1,C2 are constants (and A is "nice"). Before I multiply two sums, I reduce the fractions, maybe you don't?

sclo wrote:The problem here is getting tle for no obvious reason. I had to make weird optimizations to get AC in more than 9.3 secs.

By choosing the proper order of calculations, you never have to multiply two bigints or divide one by an other. Instead you only need multiplication of a bigint by a regular int and division by a regular int. This can save lots of time. (This under the assumption that the base of your bigints is >1000000003).