发现很多题解都没有讲清楚这道题为什么要用逆元、递推公式怎么来的。 我，风雨兼程三十载，只为写出一篇好题解。 还是我来造福大家一下吧。
题目大意：
一个长度为 n 且 1~n 各出现一次的序列，希望在“序列中有且只有 m个数的值 等于 它的位置”条件下求出序列个数。答案对1000000007取模。
题目分析：
这道题也许是加强版的“装错了的信封”，在“装错了的信封”上搞搞比利就好。我们不妨设：
值等于位置的数字 称 稳定的
值不等于位置数字 称 不稳定的
稳定的数字由于要保证 值等于位置，故 稳定的数字从序列左到右的值是递增的
首先我们根据组合数的思想可以知道：
答案 = 稳定的挑选方法数 乘上 不稳定的挑选方法数 。
所以现在我们的目的改成了求出 稳定的挑选方法数 和 不稳定的挑选方法数 。
稳定的挑选方法数：
我们已经知道了 稳定的数字从序列左到右的值是递增的，那么我们只需要模拟是哪几个数是稳定的即可。
不难想到，数量其实就是 在 (n) 个数中 挑选 (m) 个数的方案数 。
这不就是组合数里面的 (C_n^m) 吗？有 (C_n^m) = (frac{n!}{m!(n-m)!})
搞定
不稳定挑选方法数（错排）：
我们假设已经知道了哪 (m) 个数是稳定的，那么我们可以在数组中暂时只看不稳定的数。
也就是 错排
我们令数组 (F_x) 为 有 (x) 个数字，每个数字均为不稳定的方法数。
由于这些数是不稳定的，那么就没有值的大小递增关系，所以我们对于每一个 (F_x) ，都要进行分类讨论。
于是对于每个 (F_i) ，有 (F_i) = ((i - 1) imes(F_{x-1} + F_{x-2}))
所以最终答案为：((C_n^m imes)(F_{n-m}))%MOD
具体操作思路：
我们先要初始化，对于 (C_x^y) 要初始化阶乘，对于 (F_i) 要递推。
然后对于每一组数据，套 ((C_n^m imes)(F_{n-m}))%MOD 即可。
但是（还没完）：
由题意得，最终方案数可能很大（所以才要取模），我们在进行 答案累乘时，((C_n^m imes)(F_{n-m}))%MOD 可能会爆精度，我们于是要用到：
逆元（inv）
何为逆元（ (inv) ）？
比如当有 ((a div b) \% MOD) 时，防止 (b) 过大而爆精度，将 (a div b) 转化为某种简单的乘法。
若 (c) 为 (b) 的逆元，则有 ((b imes c) equiv 1 (mod 模数))
那么 ((a div b) \% MOD) = ((a div b) imes 1 \% MOD) = ((a div b) imes b imes c \% MOD) = ((a imes c) \% MOD)
即 （一个数 除以 另一个数）%模数 = （一个数 乘上 另一个数的逆元）%模数
如何将逆元应用到该题中
我们初始化逆元数组 (inv) ， (inv) 为 阶乘的逆元
那对于固定的值于模数，那个值的逆元怎么求呢？
请你参考费马小定理
直接给出答案：对于 (a \% 1000000007) 的逆元，为 (a^{1000000007-2})
搞个快速幂就好了
代码：
#include<bits/stdc++.h>
#include<cctype>
#pragma GCC optimize(2)
#define Max(a,f) a > b ? a : b
#define Min(a,b) a < b ? a : b
#define in(n) n = read()
#define out(a) write(a)
#define outn(a) out(a),putchar('
')
#define New ll
#define ll long long
#define rg register
using namespace std;
namespace IO_Optimization//优化函数
{
inline New read()//快读
{
New X = 0,w = 0;
char ch = 0;
while(!isdigit(ch))
{
w |= ch == '-';
ch=getchar();
}
while(isdigit(ch))
{
X = (X << 3) + (X << 1) + (ch ^ 48);
ch = getchar();
}
return w ? -X : X;
}
inline void write(New x)//快输
{
if(x < 0) putchar('-'),x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO_Optimization;
const int mod = 1000000000 + 7;//模数
const int MAXN = 1000000 + 2;//数组大小常量
ll a[MAXN],f[MAXN],inv[MAXN];
// 阶乘 F数组 逆元数组
inline ll ksm(ll a,ll b){//快速幂函数，求逆元
ll ans = 1;
a %= mod;
while(b)
{
if(b & 1)
ans = (a * ans) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ans;
}
int main()
{
a[0] = 1;//初始化
for(rg int i = 1;i <= MAXN; ++i)
{
a[i] = (a[i - 1] * i) % mod;//记得取模
inv[i] = ksm(a[i],mod - 2);//计算逆元
}
f[1] = 0,f[2] = 1,f[3] = 2;//初始化
for(rg int i = 4;i <= MAXN; ++i)
f[i] = ((i - 1) * (f[i - 1] + f[i - 2])) % mod;//递推公式
int T = read();//多数据输入
while(T--)
{
int n = read(),m = read(),k = n - m;//输入n、m，k纯属方便
if(!k)//如果n-m=0，那么方案数为1
{
puts("1");
continue;
}
if(m == 0)//如果没有稳定的数，那么答案直接等于F[n]
{
outn(f[n]);
continue;
}
if(k == 1)//如果n-m=1，则有0个方案
{
puts("0");
continue;
}
outn(((( a[n] * inv[k] ) % mod * inv[m]) % mod * f[k]) % mod);//输出
//上面是把除法改成乘法逆元了
}
return 0;
}