Đề 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. |
Speak Your Mind