| ENG RUS | Timus Online Judge |
Обсуждение задачи 1467. Сумма степенейGleb Dubosarskii Accepted simple approach for this problem [1] // Задача 1467. Сумма степеней 8 май 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 // Задача 1467. Сумма степеней 17 май 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] // Задача 1467. Сумма степеней 28 окт 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! // Задача 1467. Сумма степеней 12 авг 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] // Задача 1467. Сумма степеней 16 авг 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] // Задача 1467. Сумма степеней 12 сен 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... // Задача 1467. Сумма степеней 12 авг 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] // Задача 1467. Сумма степеней 22 окт 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? // Задача 1467. Сумма степеней 22 окт 2006 21:57 Yes. Victor Barinov (TNU) Nice problem! :) // Задача 1467. Сумма степеней 15 авг 2006 04:12 Pillar Should we use "High-precision"? [1] // Задача 1467. Сумма степеней 13 авг 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"? // Задача 1467. Сумма степеней 13 авг 2006 23:48 This problem can be solved using __int64 and some good idea. Good luck!
|