双序列匹配问题

先看一道题目：
链接
我们可以看到，对于点灯的代价\(a_{i}\)，
若有\(S=\Sigma{a_{i}}\leq X\)，则点灯的顺序不对\(X\)产生非法影响。
反之若\(S>X\)，则会存在不合法的方案。
令\(u=S-X\)，则我们的点灯方案必须满足节省的代价\(v\geq u\)。
不妨将一种点灯顺序看做序列\(b\)，其中\(b_{i}=a_{j} (1\leq i,j \leq n)\)
则序列\(b\)能节省的代价为\(v=\Sigma _{i=1}^{n}min{(i-1,b_{i})}\)
则题意转化为有多少种\(1\)~\(n\)的排列\(b\)，使得\(v\geq u\)
观察我们的式子\(\Sigma_{i=1}^{n}min(i-1,b_{i})\)我们可以感性理解这条式子，视作为:“\(i-1\)与\(b_{i}\)匹配”。
那么问题再次转化：有多少种匹配满足\(v\geq u\)。
此时我们有一个\(tirck\)。将两个序列合并为一个序列，降序排序。
我们设计\(dp\)状态：
（我们认为原\(b\)序列中的元素为“变点”，另外一个序列中的元素为“常点”）
\(f_{i,j,k}\)表示考虑了前\(i\)个，有\(j\)个不匹配的常点，此时节省的价值为\(k\)的方案数。
我们不妨分类讨论：
\((i)\)此时遍历到的点为变点：
\(1.\)我们不对它进行匹配，有\(f_{i,j,k}\leftarrow f_{i-1,j,k}\)
\(2.\)我们对它进行匹配（与前面的蓝点进行匹配），有\(f_{i,j,k}\leftarrow (f_{i-1,j+1,k-val_{i}}*w),(w=j+1)\)
补充解释：\(w\)为还没被匹配的常点个数，因为被匹配完剩\(j\)个，所以原本剩下\(j+1\)个。
\((ii)\)此时遍历到的点为常点
\(1.\)我们不对它进行匹配，有\(f_{i,j,k}\leftarrow f_{i-1,j-1,k}\)
\(2.\)我们对它进行匹配，有\(f_{i,j,k}\leftarrow (f_{i-1,j,k-val_{i}}*w),(w=cnt_{i-1}-j)\)
补充解释：我们维护\(cnt_{i}\)表示前\(i\)个数中变点的数量，\(cnt_{i-1}-j\)表示前\(i-1\)个数中尚未匹配的变点数量
易得\(ans=\Sigma_{i=u}^{n*(n-1)/2}f_{2n,0,i}\)
考虑时间复杂度，状态数为\(O(n^{4})\)，转移为\(O(1)\),总复杂度\(O(n^{4})\)。
考虑空间复杂度，总复杂度为\(O(n^{4})\)。
注意：本题时间限制为\(2s\)，空间限制为\(1024MB\)，需要卡空间。