Bzoj4517 [Sdoi2016]排列计数

首页 > 代码库 > Bzoj4517 [Sdoi2016]排列计数

2024-09-29 20:08:01 215人阅读

Time Limit: 60 Sec Memory Limit: 128 MB
Submit: 1207 Solved: 733

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 5000

Sample Output

0
1
20
578028887
60695423

HINT

Source

鸣谢Menci上传

数学问题组合数

恰好有m个位置正确，其他位置错排。

有错排公式的话就十分方便了。用容斥算错排大概会TLE？

 1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #define LL long long 7 using namespace std; 8 const int mxn=1000010; 9 const int mod=1e9+7;10 int read(){11     int x=0,f=1;char ch=getchar();12     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14     return x*f;15 }16 int fac[mxn],inv[mxn];17 int f[mxn];18 void init(){19     fac[0]=fac[1]=1;inv[0]=inv[1]=1;20     for(int i=2;i<mxn;i++){21         fac[i]=(LL)fac[i-1]*i%mod;22         inv[i]=((-mod/i*(LL)inv[mod%i]%mod)+mod)%mod;23     }24     for(int i=2;i<mxn;i++)inv[i]=(LL)inv[i-1]*inv[i]%mod;25     f[0]=1; f[1]=0;    f[2]=1;26     for(int i=3;i<mxn;i++)f[i]=(i-1)*((LL)f[i-1]+f[i-2])%mod;27     return;28 }29 int C(int n,int m){30     if(n<m)return 0;31     return fac[n]*(LL)inv[m]%mod*inv[n-m]%mod;32 }33 int n,m;34 int main(){35     int i,j;36     init();37     int T=read();38     while(T--){39         n=read();m=read();40         if(n<m){puts("0");continue;}41         int ans=(LL)f[n-m]*C(n,m)%mod;42         printf("%d\n",ans);43     }44     return 0;45 }

Time Limit: 60 Sec Memory Limit: 128 MB
Submit: 1207 Solved: 733
[Submit][Status][Discuss]