【题目描述】
将1到n任意排列,然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。问在所有排列中,有多少个排列恰好有k个“<”。答案对2012取模。
【输入格式】
第一行2个整数n,k。
【输出格式】
一个整数表示答案。
【样例输入】
5 2
【样例输出】
66
【数据范围】
对于30%的数据:n <= 10
对于100%的数据:k < n <= 1000,
F[i,j]=f[i-1,j](j+1)+f[i-1][j-1](i-j) i表示从1到i的数 j表示小于号个数
插入最大数e后添了一个>
或者一个<的数量
const
maxn=1000;
var
f:array[0..1000,0..1000] of longint;
n,i,j,k:longint;
begin
assign(input,'num.in');
assign(output,'num.out');
reset(input);
rewrite(output);
read(n,k);
if (k>n-1-k) then k:=n-1-k;
for i:=1 to n do
begin
f[i,0]:=1;
f[i,i-1]:=1;
end;
for i:=2 to n do
for j:=1 to k do
f[i,j]:=(f[i-1,j]*(j+1)+f[i-1,j-1]*(i-j)) mod 2012;
writeln(f[i,k]);
close(input);
close(output);
end.
另附 暴搜%30数据的版本
var
b:array[1..10] of boolean;
f:array[0..10] of longint;
n,k,i:longint;
procedure dfs(l,x,father:longint);
var
i:longint;
begin
if l=n then begin inc(f[x]); exit; end;
for i:=1 to n do
if not(b[i]) then
begin
b[i]:=true;
if father<i then dfs(l+1,x+1,i) else
dfs(l+1,x,i);
b[i]:=false;
end;
end;
begin
readln(n,k);
fillchar(b,sizeof(b),false);
fillchar(f,sizeof(f),0);
for i:=1 to n do
begin
b[i]:=true;
dfs(1,0,i);
b[i]:=false;
end;
for i:=0 to n-1 do write(f[i],' ');
end.