[文章目录]
Description
求有多少种长度为 n 的序列 A，满足以下条件：
1 ~ n 这 n 个数在序列中各出现了一次
若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的
满足条件的序列可能很多，序列数对 10^9+7 取模。
T=500000，n≤1000000，m≤1000000
第一道BZ的blog，好激动啊。（看了大师%%%的blog）
递推+组合数。
先有m个a[i]=i的方案为Cnm个。然后乘上个n-m个都不在自己的位置上的方案数。
假设f[x]表示x个数都不在自己位置上的方案数。考虑f[x+1].
如果新来的元素在m位置上，而m元素在n的位置上，f[x+1]=(n-1)*f[n-2].
如果m不在n的位置上，就说明除了n以外其他的所有n-1个元素都有一个位置不能选，和f[]数组的定义相同，所以f[x+1]=(n-1)*f[n-1].
注：（n-1）为n选择的位置的种类数。
所以就有递推式f[x]=(x-1)*(f[x-1]+f[x-2]).
考虑n和m的范围：100 0000所以进行预处理。
然后，因为mod的是一个质数，所以乘法逆元搞一下组合数就可以了。（amod-2为a的逆元）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
LL t,n,m;
LL mod=1000000007;
LL C[1001000],f[1001000];
LL pow(LL x)
{
LL re=1,y=mod-2;
while(y)
{
if(y&1) re=re*x%mod;
x=x*x%mod;y>>=1;
}
return re;
}
int main()
{
scanf("%lld",&t);
C[0]=1;C[1]=1;C[2]=2;f[2]=1;f[0]=1;
for(LL i=3;i<=1000000;i++)
{
C[i]=C[i-1]*i%mod;
f[i]=(i-1)*(f[i-1]+f[i-2])%mod;
}
while(t--)
{
scanf("%lld%lld",&n,&m);
printf("%lld\n",f[n-m]*C[n]%mod*pow(C[m])%mod*pow(C[n-m])%mod);
}
return 0;
}忘写 \n WA了两次 QAQ