BCDIV – spoj

Đề bài:

• http://vn.spoj.com/problems/BCDIV/

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:

• xem code trên ideone

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.