错位排列(D_n=(n-1)*(D_{n-1}+D_{n-2}))，表示(n)个数都不在其下标位置上的排列数。
那么题目要求的就是(C_n^m*D_{n-m})。
阶乘分母部分的逆元可以线性处理，不需要扩欧。
//13516kb 6784ms
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define MAXIN 1000000
#define p (1000000007)
typedef long long LL;
const int N=1e6+5;
int inv_fac[N],fac[N],D[N];
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
void Init()
{
D[1]=0, inv_fac[0]=inv_fac[1]=fac[0]=fac[1]=D[0]=D[2]=1;
for(int i=2; i<N; ++i){
inv_fac[i]=1ll*(p-p/i)*inv_fac[p%i]%p,
fac[i]=1ll*fac[i-1]*i%p;
}
for(int i=3; i<N; ++i) inv_fac[i]=1ll*inv_fac[i]*inv_fac[i-1]%p;
for(int i=3; i<N; ++i) D[i]=1ll*(i-1)*(D[i-1]+D[i-2])%p;
}
int main()
{
Init();
int T=read(),n,m;
while(T--)
n=read(),m=read(),printf("%lld
",(1ll*fac[n]*inv_fac[m]%p*inv_fac[n-m]%p*D[n-m]%p));
return 0;
}
考试时：这(O(n^2))的(70)分不是送吗。。然后(10^4)的范围询问那么多，离线排个序 (O(10^8)) 3s很稳吧。。
然后写，发现不过样例。。发现主要是(f[i][0])不对。比着dfs看，把规律找出来了：(f[i][0]=(i-1)*f[i-1][0]+f[i-1][1])。(之前想漏个地方)
然后数据范围错了woc！是(10^6)。
然后就(70)分了。
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define MAXIN 1000000
#define mod (1000000007)
typedef long long LL;
const int N=1505;
int T,f[N+3][N+3],g[2][10005],Ans[500005];
char IN[MAXIN],*SS=IN,*TT=IN;
struct Ques{
int x,y,id;
bool operator <(const Ques &a)const{
return x==a.x?y<a.y:x<a.x;
}
}q[500005];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
void Init()
{
LL tmp;
f[1][1]=f[2][0]=f[2][2]=1, f[1][0]=f[2][1]=0;
for(int i=3; i<N; ++i)
{
tmp=1ll*f[i-1][0]*(i-1)+(LL)f[i-1][1];
f[i][0]=(tmp%mod), f[i][i]=1;
for(int j=1; j<i; ++j)
{
tmp=1ll*f[i-1][j]*(i-j-1)+1ll*f[i-1][j+1]*(j+1)+(LL)f[i-1][j-1];
f[i][j]=(tmp%mod);
}
}
}
void Violence()
{
Init();
for(int i=1; i<=T; ++i) printf("%d
",f[q[i].x][q[i].y]);
}
void Get_Ans(int n)
{
int pos=1;
while(q[pos].x==1) Ans[q[pos].id]=q[pos].y, ++pos;
while(q[pos].x==2) Ans[q[pos].id]=std::abs(1-q[pos].y), ++pos;
int now=1,las=0; LL tmp;
g[0][0]=g[0][2]=1, g[0][1]=0;
for(int i=3; i<=n; ++i)
{
tmp=1ll*g[las][0]*(i-1)+(LL)g[las][1];
g[now][0]=(tmp%mod), g[now][i]=1;
while(!(q[pos].y) && q[pos].x==i) Ans[q[pos].id]=g[now][0], ++pos;
for(int j=1; j<i; ++j)
{
tmp=1ll*g[las][j]*(i-j-1)+1ll*g[las][j+1]*(j+1)+(LL)g[las][j-1];
g[now][j]=(tmp%mod);
while(q[pos].y==j && q[pos].x==i) Ans[q[pos].id]=g[now][j], ++pos;
}
while(q[pos].y==i && q[pos].x==i) Ans[q[pos].id]=g[now][i], ++pos;
las=now, now^=1;
}
for(int i=1; i<=T; ++i) printf("%d
",Ans[i]);
}
int main()
{
freopen("permutation.in","r",stdin);
freopen("permutation.out","w",stdout);
T=read();
int mx=0;
for(int i=1; i<=T; ++i) mx=std::max(mx,q[i].x=read()),q[i].y=read(),q[i].id=i;
if(mx<=1500) {Violence(); return 0;}
std::sort(q+1,q+1+T);
Get_Ans(mx);
fclose(stdin);fclose(stdout);
return 0;
}