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行，每行一个答案。
Sample Input
3
4 3 2
2 3 1
3 4 1
Sample Output
6
3
30
DataConstraint
Hint
【数据规模】 30%数据 T=1;1 <= n<= 10;1 <= K <= 2;0 <= P < n 60%数据 T=1;1 <= n<= 50;1 <= K <= 10;0 <= P < n 100%数据1 <= T<= 100;1 <= n <= 100;1 <= K <= 300;0 <= P < n
分析：
方法一：DP ，用f[i,j,k]表示有i个数，最大值为j，要k次交换找到最大值的可能。由上文提到的规律，可知影响答案的是最大值前面的数的排列，所以
f[i,j,k]=f[i-1,j,k]*j+sum(sum=sum+f[i-1,j,k-1]);
方法二：DP，用f[I,j,k]表示有i个数，更新j次，最大值为k的答案。
F[I,j,k]=f[i-1,j,k]*k+sum(f[I-1,j-1,l]) (1<=l<=k-1)
显然，两种方法都有区间值，可以树状数组优化，第二种稍慢一些。我就打了第二种，比赛时没有优化60分，发现最大的点才3秒，于是优化了一下就过了。后来发现第一种才是正解，各位神牛可以一试。
代码：
const hehe=1000000007; var f:array [0..100,-1..100,0..300] of int64; a,b,c:array [1..100] of longint; i,j,n,k,t,p,ans:longint; function bit(x:longint):longint; begin exit(x and -x); end; function count(n,j,t:longint):int64; var ans:int64; begin ans:=0; while t>0 do begin ans:=(ans+f[n,j,t]) mod hehe; t:=t-bit(t); end; exit(ans); end; procedure updata(n,j,t:longint;x:int64); begin while t<=k do begin f[n,j,t]:=f[n,j,t]+x; t:=t+bit(t); end; end; procedure dp; var i,j,l,t,r,ll:longint; s:int64; begin for i:=1 to k do updata(1,0,i,1); for i:=2 to n do for j:=0 to p do for l:=1 to k do begin s:=count(i-1,j-1,l-1) mod hehe; updata(i,j,l,s); t:=(((count(i-1,j,l)+hehe-count(i-1,j,l-1)) mod hehe)*l) mod hehe; updata(i,j,l,t); end; end; begin readln(t); for i:=1 to t do begin readln(a[i],b[i],c[i]); if a[i]>n then n:=a[i]; if b[i]>k then k:=b[i]; if c[i]>p then p:=c[i]; end; fillchar(f,sizeof(f),0); dp; for i:=1 to t do writeln(count(a[i],c[i],b[i])); end.
