[SDOI2016]排列计数(详解)

42 阅读 0 评论 28 点赞

我是靠谱客的博主着急羊，最近开发中收集的这篇文章主要介绍[SDOI2016]排列计数(详解)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

[SDOI2016]排列计数

题目描述
求有多少种长度为 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 行，每行一个数，表示求出的序列数

知识点：1.基于容斥原理的错位排序 。 2.逆元。3.快速幂。

分析: 题目要求恰好有 m 个数是稳定的，也就是说序列 A中恰好要有 m 个位置满足Ai=i(1<=i<=n)，因此我们要从这1~n这n个数中取出m个数来满足这一条件共有C(n,m)种可能，接下来分析余下的n-m个位置如何排列，余下的n-m个位置中每一个都要Ai != i ，了解过错位排序的同学很容易看出这就是错位排序表述。错位排序有递推公式：F(n)=(n-1)(F(n-1)+F(n-2)), F(1)=0,F(2)=1。
所以最后的答案就是C(n,m)F(n-m)%(10^9+7).

错位排序递推公式: F(n)=(n-1)(F(n-1)+F(n-2)), F(1)=0,F(2)=1。
逆元(mod为素数时，如1e9+7)：(1/k)%mod就等于(k^(mod-2)%mod).
快速幂: 在log(b)的时间复杂度内计算出a^b%mod.

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const int N=1e6+10;
const ll mod=1e9+7; 
ll a[N],f[N];
ll qpow(ll a,ll b){   //乘法快速幂模板
	ll res=1;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b=b>>1;
	}
	return res;
} 
int main(){
	
	a[0]=1,a[1]=0,a[2]=1;
	f[0]=1;f[1]=1;f[2]=2;
	for(int i=3;i<N;i++){
		a[i]=(i-1)*(a[i-1]+a[i-2])%mod; //预处理，计算出全部的F(i)(0<=i<N)，即a[i]=F(i)
		f[i]=f[i-1]*(ll)i%mod;          //预处理，计算出全部的i的阶乘,即f[i]=i!
	}
	int t;
	scanf("%d",&t);
	while(t--){     //复杂度O(N+t*log(mod-2))
		ll n,m;
		scanf("%lld %lld",&n,&m); 

		ll sum=f[n]*qpow(f[n-m]*f[m]%mod,mod-2)%mod*a[n-m]%mod; //计算C(n,m)F(n-m)%(10^9+7).
		printf("%lldn",sum);
		
		
	}
	
	
	
	
	
	
	return 0;
}