What should my program output for n=2, n=3,n=4,n=5?

Just use Horner's rule for computing the value of polynom.
The outputs are
n = 2
0
X
*
1
+
X
*
2
+

n = 3

0
X
*
1
+
X
*
2
+
X
*
3
+

I don't think more are needed.BTW how did you solve 1057 I
can't get my program to work when b = 2 x = 1 y =
maxlongint and k is close to 15.There are about 600 000 000
combinations.

Thank YOU.
>                             BTW how did you solve 1057 I
> can't get my program to work when b = 2 x = 1 y =
> maxlongint and k is close to 15.There are about 600 000
000
> combinations.
If x=1,y=2 000 000 000,b=2 and k=20 then the combination
which must be checked are less or equal to 191 508 628.


There must be a better solution than mine(backtracking)of
1057. There must be a formula for calculating the answer.
But I can not find the mathematical solution of the problem.
I guess it is connected with 'Additive Theory of Numbers'
(I don't know whether this is the English name or not. The
Bulgarian name is 'Адитивна теория на числата').

I apologize to those of you who don't know Bulgarian. It
was difficult for me to explain the solution in Bulgarian,
therefore I explained it in Bulgarian(the solution is not
complicated but I am not used to explaining solutions).
I hope the code of my program is clear enough. You can find
it at the end of the message.



Napisah optimiziran backtrack. Programata mi raboti za
2 min i 19 sec(celeron 400 MgH) pri b=2, x=1, y=2 000 000
000, k=20(vernite kombinacii sa 69 893 164). No niama
tolkova golemi test cases ,zashtoto mi e prieta za 18 sec.

Zada niama povtorenia vsiaka sledvashta stepen e po-malka
ot predhodnata.

Parvo vzimam edna stepen, posle niakoia pomalka  i taka
dokato broia na stepenite ne stane K(namereno e reshenie)
ili dokato tekushtata stepen ne e 0(niama po malka stepen
ot 0).

Za da ne stepenuvam vseki pat otna4alo, si zapazvam
stoinostite(ot stepenuvaneto) v masiv(i-tia element e b^i).
Zapazvam i sumata na purvite i stoinosti ot masiva sas
stepenite. Zna4i i-tia element ot masiva SUMS e raven
na:b^1 + b^2+...+b^i. Tazi suma mi triabva za da otriazvam
tezi kombinacii, koito niama smisal da proveriavam.

Primer1:  ako x=2 niama smisal nai-visokata stepen da e 0(
sum[0]=1).
Primer2:  ako x=6,b=2 i purvata stepen e 2 (2^2=4), niama
smisal vtorata(koiato triabva da e po-malka ot purvata)
stepen da e 0 (2^2+2^0=5, 5<6), no moje da e 1 (2^2+2^1=6,
6=6)

Ako ne sam go obiasnil iasno, nadiavam se koda po-dolu da e
dostata4no iasen.




Here is the code(Pascal) of 1057

'broi'- the answer is stored here
'step' or 'st'- means degree
'cislo' -means number

{======================================================}
var i,c,x,y,k,b,step,broi:longint;
    steps,sums:array[-1..30]of longint;
procedure depth(st,count,cislo:longint);
var i:longint;
begin
  cislo:=cislo+steps[st];
  if cislo>y then exit;
  if count=k then
    begin
      if cislo>=x then broi:=broi+1;
      exit;
    end;
  if st=0 then exit;
  for i:=st-1 downto 0 do
    if i+count+1>=k then
      if sums[i]+cislo>=x then
        depth(i,count+1,cislo);
end;
begin
  read(x,y,k,b);
  c:=1;
  for i:=0 to maxlongint do
    begin
      steps[i]:=c;
      sums[i]:=sums[i-1]+c;
      if c>y div b then
        break;
      c:=c*b;
    end;
  step:=i;
  broi:=0;
  for i:=step downto 0 do
    depth(i,1,0);
  writeln(broi);
end.
{======================================================}

I don't think they wanted backtrack.I managed to do the
real solution and it's not that complicated.It requires
10th grade combinatorics material.

> I don't think they wanted backtrack.I managed to do the
> real solution and it's not that complicated.It requires
> 10th grade combinatorics material.

What does it means 10th grade?

> > I don't think they wanted backtrack.I managed to do the
> > real solution and it's not that complicated.It requires
> > 10th grade combinatorics material.
>
> What does it means 10th grade?

10-th class.