QOJ.ac

QOJ

時間限制: 8.0 s 記憶體限制: 512 MB 總分: 100 可 Hack ✓

#16873. 水母与黑客

统计

众所周知,快速排序通过随机选择数组中的一个“基准”(pivot)元素,并根据其他元素是否小于或大于基准将它们划分为两个子数组来工作。但 Jellyfish 认为选择随机元素纯属浪费时间,因此她总是选择第一个元素作为基准。她代码运行所需的时间可以通过以下伪代码计算:

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

现在你想向她证明她的代码很慢。当函数 fun(A) 大于或等于 lim 时,她的代码会超时(Time Limit Exceeded)。你想知道有多少个 $[1, 2, \dots, n]$ 的不同排列 $P$ 满足 fun(P) >= lim。由于答案可能很大,你只需要求出答案对 $10^9 + 7$ 取模的结果。

输入格式

输入仅一行,包含两个整数 $n$ 和 $lim$ ($1 \le n \le 200, 1 \le lim \le 10^9$)。

输出格式

输出满足条件的排列数量,对 $10^9 + 7$ 取模。

样例

输入格式 1

4 10

输出格式 1

8

输入格式 2

8 32

输出格式 2

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$ 取模后的答案。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.