题目描述
求有多少种长度为 n 的序列 A,满足以下条件:
1 ~ n 这 n 个数在序列中各出现了一次
若第 i 个数 A[i] 的值为 i,则称 i 是稳定的。序列恰好有 m 个数是稳定的
满足条件的序列可能很多,序列数对 10^9+7 取模。
输入
第一行一个数 T,表示有 T 组数据。
接下来 T 行,每行两个整数 n、m。
T=500000,n≤1000000,m≤1000000
输出
输出 T 行,每行一个数,表示求出的序列数
样例输入
5
1 0
1 1
5 2
100 50
10000 5000
样例输出
0
1
20
578028887
60695423
/**************************************************************
Problem: 4517
User: ictsing
Language: C++
Result: Accepted
Time:11244 ms
Memory:16916 kb
****************************************************************/
#include<iostream>
#include<cstdio>
const int mt= 1000000+5;
const int mod= 1e9+7;
using namespace std;
long long f[mt],fac[mt];
long long quickpow(long long a,long long b)
{
long long ans=1;
a=a%mod;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod,b>>=1;
}
return ans%mod;//要勤于取mod啊QAQ
}
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
long long c(long long n,long long m)
{
if(m<0||m>n) return 0;
long long s1=fac[n],s2=fac[n-m]*fac[m]%mod;
return s1*quickpow(s2,mod-2)%mod;
}
void init()
{
fac[0]=1;
for(int i=1;i<mt;i++) fac[i]=fac[i-1]*i%mod;
f[0]=1,f[1]=0;
for(int i=2;i<mt;i++) f[i]=(f[i-1]+f[i-2])*(i-1)%mod;
}
int main()
{
init();
int t=read();
while(t--)
{
int n=read(),m=read();
printf("%lld\n",c(n,m)*f[n-m]%mod);
}
return 0;
}
/*
5
1 0
1 1
5 2
100 50
10000 5000
0
1
20
578028887
60695423
*/
评论