Jellyfish and Hack
Contest: Codeforces Round 901 (Div. 1)
Difficulty rating: 3000
Tags: dp, math

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:

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$$$.

Input format:
The only line of the input contains two integers $$$n$$$ and $$$lim$$$ ($$$1 \leq n \leq 200$$$, $$$1 \leq lim \leq 10^9$$$).

Output format:
Output the number of different permutations that satisfy the condition modulo $$$10^9+7$$$.

Constraints:
Time limit: 8.0 s
Memory limit: 512.0 MB

Note:
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$$$.

Example input:
4 10

Example output:
8

Example input:
8 32

Example output:
1280

Editorial:
Firstly, if $$$lim > \frac {n(n+1)} 2$$$, the answer will be $$$0$$$. So we only need to solve the problem which satisfies $$$lim \leq \frac{n(n+1)} 2$$$.
We can use dynamic programming to solve the problem:
Let's define $$$dp_{i, s}$$$ means the number of the permutations $$$P$$$ of $$$1, 2, \dots, i$$$, satisfying $$$\mathrm{Time(i, P)} = s$$$.
Since only relative rankings are useful, we have the following transition:
$$$dp_{0, 0} = 1$$$
$$$\forall i > 1, dp_{i, s} = \sum_{j=1}^i \binom {i-1} {j-1} \sum_{t=0}^{s - i} dp_{j - 1, t} \times dp_{i - j, s - i - t}$$$
The time complexity is $$$O(n^6)$$$, because $$$s \leq \frac {i(i+1)} 2$$$. How can it becomes faster?
Fast Fourier Transform(FFT) might come to mind first. If we use FFT instead of enumerating $$$t$$$, The time complexity will become $$$O(n^4 \log n)$$$. This is not enough because $$$n$$$ is large and $$$10^9+7$$$ is not a modulus suitable for Number-theoretic Transform (NTT).
Tips. Also, if you use divide and conquer and FFT, The time complexity will be $$$O(n^3 \text{poly}(\log n))$$$, but because FFT have a big constant factor, this still can't pass the problem.
But we do something similar to what the FFT does. We define $$$F_i = \sum_{s=1}^{\frac {n(n + 1)} 2} dp_{i, s} \times x^s$$$, then we will have the following transition:
$$$F_0=1$$$
$$$F_i = x^i \times \sum_{j=1}^i \binom{i - 1}{j - 1} F_{j-1} \times F_{i-j}$$$
For all $$$1 \leq i \leq n$$$, The degree of $$$F_i$$$ won't exceed $$$\frac {n(n+1)} 2$$$. So if we have $$$\frac{n(n+1)} 2 + 1$$$ points on $$$F_n$$$, We can get $$$F_n$$$ by Lagrange Interpolation. So we have the following transition:
$$$F_0(x) = 1$$$
$$$F_i(x) = x^i \times \sum_{j=1}^i \binom{i - 1}{j - 1} F_{j-1}(x) \times F_{i-j}(x)$$$
The time complexity of the transition and the time complexity of Lagrange Interpolation are both $$$O(n^4)$$$. It can pass the problem.