ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1467. Sum of Degrees

Accepted simple approach for this problem
Posted by Gleb Dubosarskii 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
Another accepted simple approach
Posted by 👨‍💻tproger👨‍💻[GTGU] 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.