首页 > 代码库 > 【BZOJ4517】[Sdoi2016]排列计数 组合数+错排

【BZOJ4517】[Sdoi2016]排列计数 组合数+错排

2024-09-12 17:29:38   217人阅读

【BZOJ4517】[Sdoi2016]排列计数

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

题解：易知，我们先任意选m个数是"稳定"的，方案数为C(n,m)，然后我们要求的就是剩下的n-m个都不在自己位置的方案数，其实就是错排

这里顺便复习一下错排公式（居然忘了~）

对于第n个数，我们将其放在n-1个位置中的任意一个（假设放在了m位置上），那么就有了两种情况

1.m放在了n位置上，此时剩余数还剩n-1个位置，有f[n-1]中方案

2.m没有放在n位置上，那么剩余的数就只剩了n-2个位置，此时有f[n-2]中方案

所以f[n]=(n-1)*f[n-1]*f[n-2]

本题答案就是c(n,m)*f[n-m]

只需要预处理出n!和f[]，然后用乘法逆元求出c(n,m)，因为mod是质数，所以x的逆元就是x^(mod-2)

 

#include <cstdio>#include <algorithm>#include <utility>#define mod 1000000007lltypedef long long ll;using namespace std;ll n,m,ans;ll jc[1000010],cp[1000010];ll pm(ll a,ll b){	ll ret=1;	while(b)	{		if(b&1)	ret=ret*a%mod;		a=a*a%mod,b>>=1;	}	return ret;}ll c(ll a,ll b){	return jc[a]*pm(jc[b],mod-2)%mod*pm(jc[a-b],mod-2)%mod;}void init(){	jc[0]=jc[1]=cp[0]=cp[2]=1;	ll i;	for(i=2;i<=1000000;i++)	jc[i]=jc[i-1]*i%mod;	for(i=3;i<=1000000;i++)	cp[i]=(cp[i-1]+cp[i-2])*(i-1)%mod;}int main(){	init();	int t;	scanf("%d",&t);	while(t--)	{		scanf("%lld%lld",&n,&m);		ans=c(n,m)*cp[n-m]%mod;		printf("%lld\n",ans);	}	return 0;}

 

【BZOJ4517】[Sdoi2016]排列计数 组合数+错排


联系
我们