BCDIV – spoj

Đề bài:

Thuật toán:

Gọi f[i][j] là chia i số vào n nhóm.

  • f[i][j]=f[i-1][j-1]+f[i-1][j]*j.
  • Khởi tạo f[0][0]=1.

Giải thích công thức trên:

  • Nếu đã chia được (i-1) số vào (j-1) nhóm-> bắt buộc phải chia số thứ i vào nhóm thứ j-> có f[i-1][j-1] cách
  • Nếu ta đã chia được (i-1) số vào j nhóm->có j cách để cho số thứ i vào một nhóm bắt kì->có f[i-1][j]*j

Tổng cộng có f[i-1][j-1]+f[i-1][j]*j.

Code:

const   fi      ='';
        fo      ='';
var     n, k    :int64;
        f       :array[0..25,0..25] of int64;
        i, j    :longint;
        t       :longint;
begin
        fillchar(F, sizeof(f),0);
        f[0,0]:=1;
        for i:=1 to 25 do
                for j:=1 to 25 do
                        f[i,j]:=f[i-1,j-1]+f[i-1,j]*j;
        assign(input,fi);
        reset(input);
        assign(output,fo);
        rewrite(output);
        readln(t);
        for i:=1 to t do
                begin
                        readln(n,k);
                        writeln(f[n,k]);
                end;
        close(input);close(output);
end.
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*