A6868. 「SDOI2016」排列计数
编程题
普及+/提高
知识点
题目描述
求有多少种长度为 $n$ 的序列 $A$，满足以下条件：
* $1\sim n$ 这 $n$ 个数在序列中各出现了一次；
* 若第 $i$ 个数 $A_i$ 的值为 $i$，则称 $i$ 是稳定的。序列恰好有 $m$ 个数是稳定的。
满足条件的序列可能很多，序列数对 $10^9+7$ 取模。
* $1\sim n$ 这 $n$ 个数在序列中各出现了一次；
* 若第 $i$ 个数 $A_i$ 的值为 $i$，则称 $i$ 是稳定的。序列恰好有 $m$ 个数是稳定的。
满足条件的序列可能很多，序列数对 $10^9+7$ 取模。
输入格式
第一行一个数 $T$，表示有 $T$ 组数据。
接下来 $T$ 行，每行两个整数 $n$、$m$。
接下来 $T$ 行，每行两个整数 $n$、$m$。
输出格式
输出 $T$ 行，每行一个数，表示求出的序列数。
输入输出样例
输入 #1
5 1 0 1 1 5 2 100 50 10000 5000
输出 #1
0 1 20 578028887 60695423
说明/提示
测试点 1 ~ 3：$T=1000$，$n\le8$，$m\le8$；
测试点 4 ~ 6：$T=1000$，$n\le12$，$m\le12$；
测试点 7 ~ 9：$T=1000$，$n\le100$，$m\le100$；
测试点 10 ~ 12：$T=1000$，$n\le1000$，$m\le1000$；
测试点 13 ~ 14：$T=500000$，$n\le1000$，$m\le1000$；
测试点 15 ~ 20：$T=500000$，$n\le1000000$，$m\le1000000$。
测试点 4 ~ 6：$T=1000$，$n\le12$，$m\le12$；
测试点 7 ~ 9：$T=1000$，$n\le100$，$m\le100$；
测试点 10 ~ 12：$T=1000$，$n\le1000$，$m\le1000$；
测试点 13 ~ 14：$T=500000$，$n\le1000$，$m\le1000$；
测试点 15 ~ 20：$T=500000$，$n\le1000000$，$m\le1000000$。