ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
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),
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.