310711: CF1874E. Jellyfish and Hack
Description
It is well known that quick sort works by randomly selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. But Jellyfish thinks that choosing a random element is just a waste of time, so she always chooses the first element to be the pivot. The time her code needs to run can be calculated by the following pseudocode:
function fun(A)
if A.length > 0
let L[1 ... L.length] and R[1 ... R.length] be new arrays
L.length = R.length = 0
for i = 2 to A.length
if A[i] < A[1]
L.length = L.length + 1
L[L.length] = A[i]
else
R.length = R.length + 1
R[R.length] = A[i]
return A.length + fun(L) + fun(R)
else
return 0
Now you want to show her that her code is slow. When the function $\mathrm{fun(A)}$ is greater than or equal to $lim$, her code will get $\text{Time Limit Exceeded}$. You want to know how many distinct permutations $P$ of $[1, 2, \dots, n]$ satisfies $\mathrm{fun(P)} \geq lim$. Because the answer may be large, you will only need to find the answer modulo $10^9+7$.
InputThe only line of the input contains two integers $n$ and $lim$ ($1 \leq n \leq 200$, $1 \leq lim \leq 10^9$).
OutputOutput the number of different permutations that satisfy the condition modulo $10^9+7$.
ExamplesInput4 10Output
8Input
8 32Output
1280Note
In the first example, $P = [1, 4, 2, 3]$ satisfies the condition, because: $\mathrm{fun([1, 4, 2, 3]) = 4 + fun([4, 2, 3]) = 7 + fun([2, 3]) = 9 + fun([3]) = 10}$
Do remember to output the answer modulo $10^9+7$.
Output
这个题目是关于一个特定的快速排序变体，其中“水母”总是选择数组的第一个元素作为“基准”元素。给定一个数组A，函数fun(A)计算排序所需的时间，其伪代码如下：
```plaintext
function fun(A)
if A.length > 0
let L[1 ... L.length] and R[1 ... R.length] be new arrays
L.length = R.length = 0
for i = 2 to A.length
if A[i] < A[1]
L.length = L.length + 1
L[L.length] = A[i]
else
R.length = R.length + 1
R[R.length] = A[i]
return A.length + fun(L) + fun(R)
else
return 0
```
输入输出数据格式：
输入：输入包含两个整数n和lim（1 ≤ n ≤ 200, 1 ≤ lim ≤ 10^9），其中n是数组的大小，lim是函数fun(A)的阈值。
输出：输出满足fun(P) ≥ lim的不同排列数P（P是[1, 2, ..., n]的排列）模10^9+7的结果。
示例：
输入：
4 10
输出：
8
输入：
8 32
输出：
1280
注意：在第一个示例中，P = [1, 4, 2, 3]满足条件，因为fun([1, 4, 2, 3]) = 4 + fun([4, 2, 3]) = 7 + fun([2, 3]) = 9 + fun([3]) = 10。记得输出结果模10^9+7。题目大意： 这个题目是关于一个特定的快速排序变体，其中“水母”总是选择数组的第一个元素作为“基准”元素。给定一个数组A，函数fun(A)计算排序所需的时间，其伪代码如下： ```plaintext function fun(A) if A.length > 0 let L[1 ... L.length] and R[1 ... R.length] be new arrays L.length = R.length = 0 for i = 2 to A.length if A[i] < A[1] L.length = L.length + 1 L[L.length] = A[i] else R.length = R.length + 1 R[R.length] = A[i] return A.length + fun(L) + fun(R) else return 0 ``` 输入输出数据格式： 输入：输入包含两个整数n和lim（1 ≤ n ≤ 200, 1 ≤ lim ≤ 10^9），其中n是数组的大小，lim是函数fun(A)的阈值。 输出：输出满足fun(P) ≥ lim的不同排列数P（P是[1, 2, ..., n]的排列）模10^9+7的结果。 示例： 输入： 4 10 输出： 8 输入： 8 32 输出： 1280 注意：在第一个示例中，P = [1, 4, 2, 3]满足条件，因为fun([1, 4, 2, 3]) = 4 + fun([4, 2, 3]) = 7 + fun([2, 3]) = 9 + fun([3]) = 10。记得输出结果模10^9+7。