3229. Next K Permutation

单点时限: 2.0 sec

内存限制: 256 MB

$n$ 个数有 $n!$ 种全排列情况,对所有排列排序后求第 $L$ 个到第 $R$ 个排列中逆序对数量之和。

逆序对定义(摘自 wiki):

设 $A$ 为一个有 $n$ 个数字的有序集 $(n>1)$,其中所有数字各不相同。
如果存在正整数 $i, j$ 使得 $1 \leq i \lt j \leq n$ 而且 $A_i \gt A_j$,则 $(A_i, A_j)$ 这一个有序对称为 $A$ 的一个逆序对,也称作逆序。逆序对的数量称作逆序数。

输入格式

第一行 case 数量 $T$。

接下来每一行有 3 个数,$n, L, R$ $(3 \leq n \leq 12, 1 \leq L \leq R \leq 10^9)$。

输出格式

输出逆序对总数。

样例

Input
3
3 3 5
6 720 720
8 14625 17743
Output
5
15
38745

提示

样例 1 说明:

$3$ 个数所有排列排序后及其逆序对个数:

  • $(1, 2, 3)$: $0$;
  • $(1, 3, 2)$: $1$;
  • $(2, 1, 3)$: $1$;
  • $(2, 3, 1)$: $2$;
  • $(3, 1, 2)$: $2$;
  • $(3, 2, 1)$: $3$.

第 3 个到第 5 个排列逆序对数量之和为 $1 + 2 + 2 = 5$。

29 人解决,63 人已尝试。

31 份提交通过,共有 147 份提交。

5.9 EMB 奖励。

创建: 5 年前.

修改: 4 年,8 月前.

最后提交: 1 年,5 月前.

来源: 2017 华东理工上海高校邀请赛

题目标签