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

Ural SU contest. Petrozavodsk training camp. Winter 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. Sum of Degrees

Time limit: 1.0 second
Memory limit: 64 MB
On an exam:
— Find the sum of the k-th degrees of the first N positive integers.
— That's easy. What's N?
N is unknown, solve the problem in the general case.
— So how can I find this sum if N is unknown?
— We discussed it at the lectures. The sum 1k + 2k + 3k + … + Nk for any k is a polynomial P(N) of degree k+1 with rational coefficients. For example, 1 + … + N = N(N+1)/2. Given k, find the coefficients of this polynomial.
Can you solve this problem?


An integer 0 ≤ k ≤ 30.


Output coefficients of the polynomial P(N) = Ak+1Nk+1 + AkNk + … +A1N + A0 in the form of k+2 irreducible fractions. A fraction has the form "a/b" or "−a/b", where a and b are integers, b ≥ 1, a ≥ 0. The coefficients must be given in the order of descending degrees (from Ak+1 to A0). It is not allowed to omit denominators of the fractions or leave out zero coefficients. Separate the fractions with a space.


1/2 1/2 0/1
Problem Author: Alexander Ipatov
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, January 2006
To submit the solution for this problem go to the Problem set: 1467. Sum of Degrees