BZOJ 4517--[Sdoi2016]排列计数（乘法逆元）

4517: [Sdoi2016]排列计数

Time Limit: 60 Sec Memory Limit: 128 MB
Submit: 1727 Solved: 1067

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

题目链接：

　　　　http://www.lydsy.com/JudgeOnline/problem.php?id=4517

Solution

　　显然对于一次询问，只要选定m个数放在原位，然后使其他数字都不放在原位即可。。

　　设f [ i ]表示长度为i的每一位a [ i ] ! = i的方案数。。

　　于是答案显然就是C(n,m) * f [ n-m ]。。。

　　组合数可以用乘法逆元解决。。

　　考虑怎么处理f [ i ]。。首先打表可知f [ i ]一定是(i-1)的倍数。。。

　　f[1]=0

　　f[2]=1　　f[2]/1=1

　　f[3]=2　　f[3]/2=1

　　f[4]=9　　f[4]/3=3

　　f[5]=44　 f[5]/4=11

　　f[6]=265 f[6]/5=53

　　显然可以发现 f [ i ] / ( i - 1 ) = f [ i - 1 ] + f [ i - 2 ]

　　于是 f [ i ] = ( f [ i - 1 ] + f [ i - 2 ] ) * ( i - 1 )

　　O(n)递推，O(1)询问。。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#include<vector>

#include<map>

#define pa pair<LL,LL>

#define LL long long

using namespace std;

inline LL read(){

    LL 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;

}

inline void Out(LL a){

    if(a>9) Out(a/10);

    putchar(a%10+'0');

}

const LL inf=1e9+10;

const LL mod=1e9+7;

const int N=1000050;

LL n,m;

LL f[N+50],jc[N+50],ny[N+50];

LL C(LL x,LL y){

	return jc[y]*ny[x]%mod*ny[y-x]%mod;

}

int main(){

	f[0]=1;f[1]=0;

	jc[0]=jc[1]=ny[0]=ny[1]=1;

	for(LL i=2;i<=N;++i){

		f[i]=(f[i-1]+f[i-2])%mod*(i-1)%mod;

		ny[i]=(mod-mod/i)*ny[mod%i]%mod;

	}

	for(LL i=2;i<=N;++i){

		ny[i]=ny[i-1]*ny[i]%mod;

		jc[i]=jc[i-1]*i%mod;

	}

	int T;scanf("%d",&T);

	LL ans;

	while(T--){

		n=read();m=read();

		ans=C(m,n)*f[n-m]%mod;

		Out(ans);puts("");

	}

	return 0;

}

This passage is made by Iscream-2001.

秒客网