jzoj 2542. 【NOIP2011模拟9.1】统计

发布于 2019-03-26  888 次阅读


题目描述

 对于排列(P1,P2,…,PN),定义(i,j)为逆序对当且仅当i < j且Pi > Pj。统计{1,2,…,N}的所有排列中,逆序对数量为M的排列数量。

输入

输入文件count.in第一行包含两个正整数N,M。

输出

 输出文件count.out应包含一个整数,表示满足条件的排列数除以124567的余数。

思路

找规律,得出a[i,j]:=a[i1,j]+a[i,j1]a[i1,ji]i<j

var
  n,m,i,j:longint;
  a:array [0..1001,0..1001] of longint;
begin
  readln(n,m);
  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;
  write(a[n,m+1]);
end.
]]>