A6773 | $「THUPC 2024」排列游戏$

来源官方 / 2024

时间限制2500ms

内存限制512MB

通过 / 提交0/0

题目描述

有 $n$ 个格子排成一行，从左到右依次编号为 $1,2,\cdots,n$，每个格子上有一个数字卡片，初始状态下，格子 $i$ 上的卡片数字为 $i$。 打乱者会进行 $n$ 次交换操作来排列这些卡片：每次选择两个格子 $i,j$（$i\ne j$），然后交换格子 $i$ 和格子 $j$ 上的卡片。$n$ 次交换操作结束后，就完成了对卡片的排列。 然后轮到玩家行动，玩家同样需要用交换操作，每次交换两张卡片，目标是将这些卡片的顺序还原到初始状态。 交换格子 $i$ 和格子 $j$ 上的卡片所需的时间为 $|i-j|$，玩家打算用最短的时间还原该排列。问：有多少种可能的排列，玩家可以用不超过 $m$ 的总时间完成还原？两种排列不同，当且仅当至少有一张数字卡片在两种排列中所在的格子不同。

每个测试点由多组数据组成。 第一行包含一个正整数 $T$，表示数据组数。保证 $T\le1,000$。 之后 $T$ 行，每行一组数据，包含两个正整数 $n$，$m$。保证 $2\le n\le500$，$m\le5,000$。

每组数据输出一行，一个整数表示答案。 由于答案可能很大，请输出答案对 $1,000,000,007$ 取模的结果。

输入 #1

输出 #1

C++ 编辑器

输入

输出