| ENG RUS | Timus Online Judge |
Discussion of Problem 1467. Sum of DegreesGleb Dubosarskii Accepted simple approach for this problem [1] // Problem 1467. Sum of Degrees 8 May 2017 19:41 It is easy to solve this problem by using such recursive formula (k+1)P_k(N)=(N+1)^(k+1)-1-sum_(l=0)^(k-1) C_(k+1)^l P_l(N), where P_k(N) is a sum of powers k from 1 up to N, C_k^l is a binomial coefficient. I assume that P_0(N)=N. You can check this formula by summing up from 1 to N following identities (n+1)^k-n^k=sum_(l=0)^(k-1) C_k^l n^l. However, P_k(x) has non-integer coefficients, so it is better to introduce polynomials Q_k(x) by formula Q_k(x)=(k+1)!P_k(x). It can be proven by induction based on recursive formula above that Q(x) has integer coefficients!!! So, use BigIntegers in Java, otherwise you would have overflow. Good luck! Edited by author 08.05.2017 19:44 Edited by author 08.05.2017 19:44 👨💻tproger👨💻[GTGU] Another accepted simple approach // Problem 1467. Sum of Degrees 17 May 2019 19:39 You can make a system of linear equations with k+2 variables and equations, which would look like: A_0 * 1^0 + A_1 * 1^1 + ... + A_(k+2) * 1^(k+2) = 1^k A_0 * 2^0 + A_1 * 2^1 + ... + A_(k+2) * 2^(k+2) = 2^k ... A_0 * (k+2)^0 + A_1 * (k+2)^1 + ... + A_(k+2) * (k+2)^(k+2) = (k+2)^k So, you only need to find A_i coefficients using Gaussion elimination. EfremovAleksei I don't understand, how to solve this using int64! [1] // Problem 1467. Sum of Degrees 28 Oct 2006 22:51 I spent about 10 hours and got AC. I write long racional arithmetic. Please, send me prog with int64 only (efrcom [at] yandex [dot] ru) Edited by author 28.10.2006 22:51 Denis Koshman Re: I don't understand, how to solve this using int64! // Problem 1467. Sum of Degrees 12 Aug 2008 05:28 Just reduce as much as possoble before actual operation: tf operator + (const tf& f1, const tf& f2) { int64 d = gcd(f1.b, f2.b); int64 m1 = f2.b/d; int64 m2 = f1.b/d; return tf(f1.a*m1 + f2.a*m2, f1.b*m1); } tf operator - (const tf& f1, const tf& f2) { int64 d = gcd(f1.b, f2.b); int64 m1 = f2.b/d; int64 m2 = f1.b/d; return tf(f1.a*m1 - f2.a*m2, f1.b*m1); } tf operator * (const tf& f1, const tf& f2) { int64 d1 = gcd(f1.a, f2.b); int64 d2 = gcd(f2.a, f1.b); return tf((f1.a/d1)*(f2.a/d2), (f1.b/d2)*(f2.b/d1)); } tf operator / (const tf& f1, const tf& f2) { assert(f2.a); return f1*tf(f2.b, f2.a); } fractions are further reduced inside 'tf(int64, int64)' constructor. Edited by author 12.08.2008 05:28 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 frost what's the answer of n=30? [1] // Problem 1467. Sum of Degrees 22 Oct 2006 15:38 is it 1/31 1/2 5/2 0/1 -203/6 0/1 1131/2 0/1 -16965/2 0/1 216775/2 0/1 -2304485/2 0/1 19959975/2 0/1 -137514723/2 0/1 731482225/2 0/1 -31795091601/22 0/1 8053785025/2 0/1 -102818379585/14 0/1 15626519181/2 0/1 -23749461029/6 0/1 8615841276005/14322 0/1 ? UdSU: Ajtkulov, Kotegov, Saitov Re: what's the answer of n=30? // Problem 1467. Sum of Degrees 22 Oct 2006 21:57 Yes. Victor Barinov (TNU) Nice problem! :) // Problem 1467. Sum of Degrees 15 Aug 2006 04:12 Pillar Should we use "High-precision"? [1] // Problem 1467. Sum of Degrees 13 Aug 2006 18:05 When I use "int" data type,I can pass 8 tests,When I use "__int64" data type,I can pass 16 tests. Does it mean that we should use "High-precision" to pass all the tests? Thanx! Sandro (USU) Re: Should we use "High-precision"? // Problem 1467. Sum of Degrees 13 Aug 2006 23:48 This problem can be solved using __int64 and some good idea. Good luck!
|