there is my program


var
c:array[0..1800] of real;
n,m,i ,fn:longint;
begin
readln(n,m);
c[0]:=1;
c[1]:=m-1;
i:=1;
repeat
i:=i+1;
{for i:=2 to n do   }
c[i]:=(m-1)*(c[i-1]+c[i-2]);
until i>=n;
writeln(c[n]:0:0);
end.

there is my program


var
c:array[0..1800] of real;
n,m,i ,fn:longint;
begin
readln(n,m);
c[0]:=1;
c[1]:=m-1;
i:=1;
repeat
i:=i+1;
{for i:=2 to n do   }
c[i]:=(m-1)*(c[i-1]+c[i-2]);
until i>=n;
writeln(c[n]:0:0);
end.

as you know, it is forbidden to use math.
but then how to use log?

tell me wht doesn't this program work? or at least tell me an example that my program doesn't give us the right answer

var
       l,n,k :integer;
       sum   :longint;

function c(a,b:integer):integer;
   var
       i,a1,b1,a1b1:integer;
   begin
       a1:=1;
       for i:=1 to a do
          a1:=a1*i;
       b1:=1;
       for i:=1 to b do
          b1:=b1*i;
       a1b1:=1;
       for i:=1 to a-b do
          a1b1:=a1b1*i;
       c:=a1 div (b1*a1b1);
   end;

function power(r,s:integer):integer;
   var
       j,rs:integer;
   begin
       rs:=1;
       for j:=1 to s do
           rs:=rs*r;
       power:=rs;
   end;



begin
     readln(n,k);
     l:=-1;
     while 2*l<=n do
     begin
           inc(l);
           inc(sum,(c(n-l,l)*power(k-1,n-l)));
     end;
     writeln(sum);
end.

After A lot of attemps I Got AC with pretty desent times (according to me :) ):
http://acm.timus.ru/status.aspx?space=1&num=1013&author=40769.

I wonder, is it possible??
http://acm.timus.ru/status.aspx?space=1&author=43335

He uses only 2 K memory

Edited by author 06.07.2006 22:21

Edited by author 06.07.2006 22:21

Here is my code

#include<stdio.h>
long len[2],a[2][10000];
sum(int x)
{
    int i;
    for(i=9999;i>=10000-len[(x)%2];i--)
    {
        a[(x-1)%2][i] = a[x%2][i] + a[(x-1)%2][i];
        if(a[(x-1)%2][i]>=10)
        {
            a[(x-1)%2][i] = a[(x-1)%2][i]%10;
            a[(x-1)%2][i-1]++;
            if(i==10000-len[(x-1)%2])
                len[(x-1)%2]++;
        }
    }
    return 0;
}
multiply(int x,int k)
{
    int i,tod;
    tod=0;
    for(i=9999;i>=10000-len[(x-1)%2];i--)
    {
        a[(x-1)%2][i] = a[(x-1)%2][i] * k+tod;
        tod = 0;
        if(a[(x-1)%2][i]>=10)
        {
            tod = a[(x-1)%2][i]/10;
            a[(x-1)%2][i] = a[(x-1)%2][i]%10;
            if(i==10000-len[(x-1)%2])
                len[(x-1)%2]++;
        }
    }
    return 0;
}

main()
{
    long n,k,i,tmp;
    scanf("%ld %ld",&n,&k);
    a[0][9999] = 1;
    a[1][9999] = k-1;
    len[0] = 1;
    len[1] = 1;
    for(i=1;i<n;i++)
    {
        sum(i);
        multiply(i,k-1);
    }
    tmp = i;
    for(i=10000-len[tmp%2];i<=9999;i++)
        printf("%ld",a[tmp%2][i]);
    return 0;
}

That's just great! I had WA on it after it was AC as 1012, then I was looking for mistakes for like half an hour! And finaly I submitted it with no changes and getting AC!!!

#include <stdio.h>
#include <mem.h>
int num[2000],temp[2000],n,k,c1,c2;
void jian()
{
  int i,tw=0;
  for (i=1998;i>=0;i--)
  {
    if ((num[i]-temp[i]-tw)<0) {num[i]=10+num[i]-temp[i]-tw;tw=1;}
    else {num[i]=num[i]-temp[i]-tw;tw=0;}
    if (i<c2) {c2=i;break;}
  }
}
void cheng(int m)
{
  int i,j,jw,t;
  for (i=1;i<=m;i++)
  {
    jw=0;
    for (j=1998;j>=0;j--)
    {
      t=temp[j];
      temp[j]=(k*temp[j]+jw)%10;
      jw=(k*t+jw)/10;
      if ((j<=c1)&&(jw==0)) {c1=j;break;}
    }
  }
  i=1998;
  while (i>=0)
  {
    if (temp[i]>0) {temp[i]--;break;}
    else {temp[i]=9;i--;}
  }
}
int main()
{
  int i,j;
  scanf("%d %d",&n,&k);
  c2=0;
  for (i=n;i>=1;i--)
  {
    for (j=0;j<=1998;j++) temp[j]=0;
    temp[1998]=1;
    c1=1998;
    cheng(i);
    if (i==n) for (j=0;j<=1998;j++) num[j]=temp[j];
    else jian();
  }
  for (i=0;i<=1998;i++)
    if (num[i]!=0) {j=i;break;}
  for (i=j;i<=1998;i++)
    printf("%d",num[i]);
  printf("\n");
  return 0;
}

I use C, & I tryed to use unsigned long long with base 1e18, but it
gives me Compilation Error, so I changed long long to int and then
all works well.
On gnu gcc 3.1 it works well also with long long.
Isn't a iso/ansi c standard feature?
What is the compiler used here?

I made my array 10000, but still WA.

type
  arr=array [1..10000] of byte;
var
    p1,p2,p3,p4:arr;
    i,j,k,n,pos1,pos2,pos3,pos4:integer;
procedure init;
  begin
  read(n,k);
  p2[1]:=1;
  p3[1]:=k-1;
  pos2:=1;
  pos3:=1;
  end;
procedure plus(p1,p2:arr);
  var i:integer;
  begin
   fillchar(p4,sizeof(p4),0);
   for i:=1 to pos2 do
     begin
     inc(p4[i],p1[i]+p2[i]);
     if p4[i]>=10
       then begin
            inc(p4[i+1],p4[i] div 10);
            p4[i]:=p4[i] mod 10;
            end;
     end;
   if pos1=pos2
     then begin
          if p4[pos2+1]>0 then pos4:=pos2+1
                          else pos4:=pos2;
          end
     else pos4:=pos2;
  end;
procedure multiply(m:integer;p4:arr);
  var i:integer;
      judge:boolean;
  begin
   fillchar(p3,sizeof(p3),0);
   for i:=1 to pos4 do
    begin
    inc(p3[i],m*p4[i]);
    if p3[i]>=10
      then begin
            inc(p3[i+1],p3[i] div 10);
            p3[i]:=p3[i] mod 10;
           end;
    end;
   inc(i); judge:=true;
   while p3[i]>=10 do
     begin
     inc(p3[i+1],p3[i] div 10);
     p3[i]:=p3[i] mod 10;
     inc(i); judge:=false;
     end;
   if (judge)and(p3[i]=0) then pos3:=i-1
   else pos3:=i;
  end;
begin
  init;
  for i:=2 to n do
    begin
    p1:=p2; p2:=p3;
    pos1:=pos2; pos2:=pos3;
    plus(p1,p2);
    multiply(k-1,p4);
    end;
  for i:=pos3 downto 1 do
   write(p3[i]);
  writeln;
end.

578757056862334899165386755574542961035018961384746496922121998413414
760578182667592445243789096415796683784227403924744723018491482416669
583482398922538253661908580120448244915999799871558380368176603050559
510718284952242760194267347067123980934918801967607536469254034237855
004802696022500822172028398423844181519062416396935137327709596075152
735669152169110801968382442244041567095126300108993003699366100747388
317910001503702242232876832468136833706279128186553604889872071700426
036131859303238586562176695339522070686158319498115704647672049305508
967900683916271481984259265546356412140086789757225512541731310323935
465682724467659536689371357372914882072915082178670642329922381122275
468063370016704705831888401388113877883071853045716833529742834352672
724383287190741642453977167289524175574818905457159394451552772137292
488320334403152854433233102668615521440710891545314660751974297836931
960344433170067572075073148241931611479767495629397929628139141880637
989092914568731174905142673360305672949338207556968549473017117468827
284519728547200726208072433397564194838002665675662311399400888368781
978474075164605331088146108539042375572214938643357857365785518398241
331586137392525667520443971761280252462702157845931972397850694852408
175842881290034219718513679989695433894555165544194154985658919590072
834353665620602624018084160454588232743604457892810545037909657962721
015357460269322147036550672667818736987298257001343500000127759081331
342259975035657526096273951774789390285967686426895591017628858005630
345299494887070844487552423092400976960882414257386427295509443688581
404929103326521825760465770078754255614451223600182778301246454644360
519407068303890382956047923339271967598500824214773103912508358944293
85287661810322936028474039484807146122948136437705880627901328134001

program kbasednumbers;
 const max=500;
       osn=100000000;
 type big=array[0..max] of longint;
  var i:integer;
      a,b,c:big;
      n,k:word;

  procedure sumbig(var a,b,c:big);
   var k,i:word;
    begin
      FillChar(c,sizeof(c),0);
      if a[0]>=b[0] then k:=a[0] else k:=b[0];
      for i:=1 to k do begin
        c[i+1]:=(a[i]+b[i]+c[i]) div osn;
        c[i]:=(a[i]+b[i]+c[i]) mod osn;
      end;
      if c[k+1]<>0 then c[0]:=k+1 else c[0]:=k;
    end;

  procedure multbignum(var a:big; number:word);
   var k,i:word;
       um,um_temp:longint;
    begin
      um:=0;
      for i:=1 to a[0] do begin
        um_temp:=(um+a[i]*number) div osn;
        a[i]:=(um+a[i]*number) mod osn;
        um:=um_temp;
      end;
      if um<>0 then begin inc(a[0]); a[a[0]]:=um; end;
    end;

  procedure printbig(var a:big);
   var nosn:word;
       s:string;
    begin
      str(osn div 10,s);
      nosn:=length(s);
      write(a[a[0]]);
      for i:=a[0]-1 downto 1 do begin
        str(a[i],s);
        while length(s)<nosn do s:='0'+s;
        write(s);
      end;
    end;

begin
 read(n);
 read(k);
 a[0]:=1;
 a[1]:=1;
 b[0]:=1;
 b[1]:=k-1;
 for i:=2 to n do begin
   sumbig(a,b,c);
   multbignum(c,k-1);
   a:=b;
   b:=c;
 end;
 printbig(b);
end.

const nn=100;
type my=array[1..nn]of integer;
var a,b,c:my;
    n,k:integer;
function dlina(a:my):integer;
var i:integer;
begin
 i:=nn;
 while a[i]=0 do dec(i);
 dlina:=i;
end;
procedure mul(a:my;var c:my);
var i:integer;
    d:integer;
begin
 fillchar(c,sizeof(c),0);
 d:=dlina(a);
 for i:=1 to d do
  c[i]:=a[i]*k;
 for i:=1 to d do
  if c[i]>9 then
   begin
    inc(c[i+1],c[i] div 10);
    c[i]:=c[i] mod 10;
   end;
 while c[d+1]<>0 do
  begin
   inc(d);
   if c[d]>9 then
    begin
     c[d+1]:=c[d] div 10;
     c[d]:=c[d] mod 10;
    end;
  end;
end;
procedure slog(a,b:my;var c:my);
var d1,d2,max,i:integer;
begin
 fillchar(c,sizeof(c),0);
 d1:=dlina(a);
 d2:=dlina(b);
 if d1>d2 then max:=d1 else max:=d2;
 for i:=1 to max do
  begin
   c[i]:=c[i]+a[i]+b[i];
   if c[i]>9 then
    begin
     inc(c[i+1]);
     c[i]:=c[i] mod 10;
    end;
  end;
end;
procedure init;
begin
 assign(input,'');
 reset(input);
  readln(n);
  readln(k);
 close(input);
end;
procedure solve;
var i:integer;
    s:string;
begin
 dec(k);
 str(k,s);
 for i:=1 to length(s) do
  c[i]:=ord(s[length(s)-i+1])-48;
 for i:=2 to n do
  begin
   a:=b;
   b:=c;
   slog(a,b,c);
   mul(c,c);
  end;
 slog(b,c,c);
end;
procedure out;
var i:integer;
begin
 assign(output,'');
 rewrite(output);
  for i:=dlina(c) downto 1 do
   write(c[i]);
 close(output);
end;
begin
 init;
 solve;
 out;
end.

F[N] = (k-1)*(F[N-1]);
F[L] = (K-1)* (F[L-1] + F[L-2]);
F[0] = 0;
F[1] = K;
Does it correct ?
help me please.

program p1013;
const mx=120;
type arr=array[1..mx] of longint;
var a:array[0..1800] of arr;
n,k,k1,t,i,j:integer;

begin
 readln(n); readln(k);
 fillchar(a,sizeof(A),0);
 k1:=k-1; t:=1;
 while k1>0 do
 begin
  a[1,t]:=k1 mod 10;
  k1:=k1 div 10; inc(t);
 end;
 a[0,1]:=1;
 for i:=2 to n do
 begin
   for j:=1 to mx do a[i,j]:=a[i,j]+a[i-1,j]+a[i-2,j];
   for j:=1 to mx do a[i,j]:=a[i,j]*(k-1);
   for j:=1 to mx do a[i,j+1]:=a[i,j+1]+a[i,j] div 10;
   for j:=1 to mx do a[i,j]:=a[i,j] mod 10;
 end;
 i:=50; while a[n,i]=0 do dec(i);
 for j:=i downto 1 do write(a[n,j]);
 writeln;
end.

  The algorithms I found requires O(N^2) , which N = 1800 . But we
must calculate the large-number ( I use string) , so it takes about O
(N^3) !!! . Could anyone help me on this Problem  ?

long-number arithmetic?
i thank that the resulting number is the next summ:
  N
 ___ i        i
 \_ C   *(K-1)
 /__ N-i

i=[N/2],   where C is  i!/((N-i)!*(2*i-N)!)

and so we have to apply a long-number arithmetic,am I right?
but it is no so fast for this problem!i get a time limit exceeded
(it was worked for #1012)
help me please
maybe there are another faster algorithm?

here is my program

program ff;
  var
    n,i,j,k,l,t:integer;
    u0,u1,u2,a,b,c:array[0..2000] of byte;

  function max(a,b:integer):integer;
    begin
      if a>b then max:=a else max:=b;
    end;

  procedure sum(a,b:array of byte);
    begin
      l:=max(a[0],b[0]);
      fillchar(c,sizeof(c),0);
      t:=0;
      for i:=1 to l do begin
        c[i]:=(a[i]+b[i]+t) mod 10;
        t:=(a[i]+b[i]+t) div 10;
      end;
      c[0]:=l;
      if t<>0 then begin
        c[0]:=l+1;
        c[l+1]:=t;
      end;
    end;

  procedure mult(a:array of byte);
    begin
      l:=k-1;
      t:=0;
      fillchar(c,sizeof(c),0);
      for i:=1 to a[0] do begin
        c[i]:=(l*a[i]+t) mod 10;
        t:=(l*a[i]+t) div 10;
      end;
      c[0]:=a[0];
      if t<>0 then begin
        c[0]:=a[0]+1;
        c[c[0]]:=t;
      end;
    end;

  procedure solve;
    begin
      u0[1]:=1; u0[0]:=1;
      u1[1]:=k-1; u1[0]:=1;
      for j:=2 to n do begin
        sum(u0,u1);
        u2:=c;
        mult(u2);
        u2:=c;
        u0:=u1;
        u1:=u2;
      end;
    end;

  begin
    readln(n,k);
    solve;
    for i:=u2[0] downto 1 do write(u2[i]);
    writeln;
  end.