Discussion @ 1467. Sum of Degrees @ Timus Online Judge

Levan K I use maple to find formula... [2] // Problem 1467. Sum of Degrees 16 Aug 2006 13:16

I think, i will find the formula maple 10 best for symbol symplification.

if any body got formula. don't hide :)

Blum Re: I use maple to find formula... [1] // Problem 1467. Sum of Degrees 12 Sep 2006 19:42

I found formula using my math.(it's recursive, but it was rather easy to get AC using __int64)

Denis Koshman Re: I use maple to find formula... // Problem 1467. Sum of Degrees 12 Aug 2008 04:59

f(K, N) = 1^k + ... + N^k =
= A[k,k+1]*N^(k+1) + ... + A[k,0]*N^0

f(K, N) = 1^(K-1)*1 + 2^(K-1)*2 + .. + N^(K-1)*N =
= (1^(K-1) + ... + N^(K-1)) +
+ (2^(K-1) + ... + N^(K-1)) + ... + (N^(K-1)) =
= f(K-1, N) + (f(K-1, N) - f(K-1, 1)) + ... + (f(K-1, N) - f(K-1, N-1)) =
= (N+1)*f(K-1, N) - S(K-1, N)

S(K, N) = f(K, 1) + ... + f(K, N)

S(K, N) = A[K,K+1]*(1^(K+1) + ... + N^(K+1)) +
+ A[K, K]*(1^K + ... + N^K) + ... + A[K,0]*(1^0 + ... + N^0) =
A[K,K+1]*f(K+1, N) + A[K,K]*f(K, N) + ... + A[K,0]*f(0, N)

So, overally:

f(K, N) = (N+1)*f(K-1, N) - S(K-1, N)
S(K-1, N) = A[K-1,K]*f(K, N) + A[K-1,K-1]*f(K-1, N) + ... + A[K-1,0]*f(0, N)

Edited by author 12.08.2008 05:00

Discussion of Problem 1467. Sum of Degrees