最大值 (Standard IO)

Description

　　找到一個數組的最大值的一種方法是從數組開頭從前到後對數組進行掃描，令max=a[0] (數組下表從0..N-1)，如果a[i]>max，就更新max，這樣就可以在O(N)的時間裡找到一個數組的最大值。

　　這個問題是相當簡單的，但是想到了另一個問題，如果一個包含N個元素的數組a裡面的元素的值是在1…K之間的整數，存在多少個不同的數組a，進行了如上掃描之後，max恰好進行了P次更新?

　　下面是N = 4，K = 3，P = 2時所有情況

　　1) {1,1,2,3}

　　2) {1,2,1,3}

　　3) {1,2,2,3}

　　4) {1,2,3,1}

　　5) {1,2,3,2}

　　6) {1,2,3,3}

　　共有6種情況

　　由于答案可能很大，是以你僅僅需要把答案mod (10^9+7)輸出。

Input

　　輸入檔案findmax.in的第一行T，本題有T組資料。

　　接下來T行，每行三個整數N,K,P

Output

　　輸出檔案findmax.out包括T行，每行一個答案。

題解

用DP做的,數組f[i,j,k]表示i位之前最大的數為j,并且已經更新了k次的方案數。

那麼f[i,j,k]=f[i-1,q,k-1]+f[i-1,j,k]*j,其中q為所有小于j數字。

因為當我們在最後一位加入j時,所有第i位之前最大的數比j小的方案都會更新一次,是以要加上所有的f[i-1,q,k-1]，q要小于k。

如果第i位之前最大的數已經為j,則本次不會更新,但第i位可以填入任何比j小的數,是以加上f[i-1,j,k]*j。

最後輸出的答案為i=n,k=p時j從1到m的所有方案數。

裸的話會逾時,用字首和優化一下第二步。

空間方面可以用滾動數組。

代碼

const
  mood=;

var
  t,n,m,p:longint;
  f,b:array [..,..] of int64;
  ans:int64;
function min(o,p:longint):longint;
begin
  if o<p then exit(o);
  exit(p);
end;

procedure main;
var
  i,j,k,l:longint;
begin
  for l:= to t do
    begin
      fillchar(f,sizeof(f),);
      fillchar(b,sizeof(b),);
      readln(n,m,p);
      for i:= to m do
        begin
          f[i,]:=; b[i,]:=i;
        end;
      for i:= to n do
        for k:=min(i-,p) downto  do
          for j:= to m do
            begin
              f[j,k]:=(f[j,k]*j) mod mood;
              if k> then
                  f[j,k]:=(f[j,k]+b[j-,k-]) mod mood;
              b[j,k]:=b[j-,k]+f[j,k];
            end;
      ans:=;
      for i:= to m do
        ans:=(ans+f[i,p]) mod mood;
      writeln(ans);
    end;
end;

begin
  readln(t);
  main;
end.