PID619 / 最大值
题目描述

lqp在回忆自己初学OI的经历,他想起了自己学习如何找数组最大值的时候......

找到一个数组的最大值的一种方法是从数组开头对数组进行扫描,令max=a[0](数组下表从0..N-1),如果a_i>max,就更新max,这样就可以在O(N)的时间里找到一个数组的最大值。

这个问题是相当简单的,但是lqp想到了另一个问题,如果一个包含N个元素的数组a里面的元素的值是在1...K之间的整数,存在多少个不同的数组a,进行了如上扫描之后,max恰好进行了p次更新?

这个问题把lqp难住了,于是他想请你帮他算算。

下面是lqp手算的一组数据: 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种情况

由于答案可能很大,lqp讨厌很大的数,所以你仅仅需要把答案mod 10^9+7输出。

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

输入格式

第一行T,本题有T组数据。

接下来T行,每行三个整数,N,K,P.

输出格式

T行,每行一个答案

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论