题意/Description:
对于排列(P1,P2,...,PN),定义(i,j)为逆序对当且仅当i < j且Pi > Pj。统计{1,2,...,N}的所有排列中,逆序对数量为M的排列数量。
读入/Input:
输入文件count.in第一行包含两个正整数N,M。
输出/Output:
输出文件count.out应包含一个整数,表示满足条件的排列数除以124567的余数。
题解/solution:
大家要的公式,当m<=n时,F[n,m]=F[n-1,m]+F[n,m-1];
否则,F[n,m]=F[n-1,m]+F[n,m-1]-F[n-1,m-n];
代码/Code:
var
n,m:longint;
a:array [0..1001,0..1001] of longint;
procedure main;
var
i,j:longint;
begin
a[1,1]:=1;
for i:=2 to n do
for j:=1 to m+1 do
if j<=i then a[i,j]:=(a[i-1,j]+a[i,j-1]) mod 124567
else a[i,j]:=(a[i-1,j]+a[i,j-1]-a[i-1,j-i]+124567) mod 124567;
end;
begin
readln(n,m);
main;
write(a[n,m+1]);
end.