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

先枚举有哪些数字满足Ai=i，那么就变成了经典的错排问题。

错排问题的递推式f[n]=(f[n-1]+f[n-2])*(n-1)。

我们考虑这n个人中编号最小的人i，设他站到了j号位置。

1.如果j号人站到了i号位置，问题转化成一个n-2的错排问题。

2.如果j号人没有站到i号位置，那么除去i号人所有人都站错了，问题转化成一个n-1的错排问题。

预处理一下阶乘即逆元即可。

#include<cstdio>

#include<cctype>

#include<queue>

#include<cstring>

#include<algorithm>

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define ren for(int i=first[x];i;i=next[i])

using namespace std;

const int BufferSize=1<<16;

char buffer[BufferSize],*head,*tail;

inline char Getchar() {

	if(head==tail) {

		int l=fread(buffer,1,BufferSize,stdin);

		tail=(head=buffer)+l;

	}

	return *head++;

}

inline int read() {

    int x=0,f=1;char c=Getchar();

    for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;

    for(;isdigit(c);c=Getchar()) x=x*10+c-'0';

    return x*f;

}

typedef long long ll;

const int maxn=1000010;

const int mod=1000000007;

int xp[maxn],inv[maxn],f[maxn];

int C(int n,int m) {return (ll)xp[n]*inv[m]%mod*inv[n-m]%mod;}

void init(int n) {

	xp[0]=inv[0]=inv[1]=1;

	rep(i,1,n) xp[i]=(ll)xp[i-1]*i%mod;

	rep(i,2,n) inv[i]=(ll)inv[mod%i]*(mod-mod/i)%mod;

	rep(i,1,n) inv[i]=(ll)inv[i-1]*inv[i]%mod;

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

	rep(i,3,n) f[i]=(ll)(f[i-1]+f[i-2])*(i-1)%mod;

}

int A[maxn],B[maxn];

int main() {

	int n=read(),m=0;

	rep(i,1,n) m=max(m,A[i]=read()),B[i]=read();

	init(m);

	rep(i,1,n) {

		if(B[i]>A[i]) puts("0");

		else printf("%d\n",(ll)C(A[i],B[i])*f[A[i]-B[i]]%mod);

	}

	return 0;

}

巴特西