题目描述
Description
求有多少种长度为 n 的序列 A，满足以下条件：
1 ~ n 这 n 个数在序列中各出现了一次
若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的
满足条件的序列可能很多，序列数对 10^9+7 取模。
Input
第一行一个数 T，表示有 T 组数据。
接下来 T 行，每行两个整数 n、m。
T=500000，n≤1000000，m≤1000000
Output
输出 T 行，每行一个数，表示求出的序列数
Sample Input
5
1 0
1 1
5 2
100 50
10000 5000Sample Output
0
1
20
578028887
60695423题目分析
首先我们在这个数列里随机选出n个数 让他们在自己的位置上 并使得剩下的n-m个数错排
令f[i]为i个数错排的方案数
然后就是错排公式的推导
假设有n封信，第一封信可放在(2-n)的任一个信封里，共n-1种放法，设第一封信放在了第k个信封里，若此时第k封信放在了第1个信封里，则只要将剩下的n-2错排，即f(n-2)，若第k封信没有放在了第1个信封里，可将第1封信的位置看成是“第k个位置”，即将n-1封信错排，即为f(n-1)
由递推可得,f(n)=(n-1)*(f(n-1)+f(n-2))
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
long long f[1001010];
int n,m,t;
long long mod=1000000007ll;
long long jie[1001010];
long long yuan[1001010];
long long ksm(long long x,long long y)
{
long long sum=1;
while(y)
{
if(y&1) sum=(sum*x)%mod;
y>>=1,x=(x*x)%mod;
}
return sum;
}
void init()
{
f[0]=1,f[1]=0,f[2]=1;
for(int i=3;i<=1000000;i++)
f[i]=(i-1)*(f[i-1]+f[i-2])%mod;
jie[0]=1;
for(int i=1;i<=1000000;i++) jie[i]=(jie[i-1]*i)%mod;
yuan[1000000]=ksm(jie[1000000],mod-2);
for(int i=1000000-1;i>=0;i--) yuan[i]=(yuan[i+1]*(i+1))%mod;
}
long long get(int x,int y)
{
return ((jie[x]*yuan[y])%mod*yuan[x-y])%mod;
}
int main()
{
scanf("%d",&t);
init();
while(t--)
{
scanf("%d%d",&n,&m);
printf("%lld\n",get(n,m)*f[n-m]%mod);
}
return 0;
}
