题意

题目描述

求有多少种长度为 n 的序列 A，满足以下条件：

1 ~ n 这 n 个数在序列中各出现了一次

若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的

满足条件的序列可能很多，序列数对 109+710^9+7109+7 取模。

输入输出格式

输入格式：

第一行一个数 T，表示有 T 组数据。

接下来 T 行，每行两个整数 n、m。

输出格式：

输出 T 行，每行一个数，表示求出的序列数

输入输出样例

输入样例#1：
复制

输出样例#1：
复制

说明

测试点 1 ~ 3： T=1000T = 1000 T=1000，n≤8 n \leq 8 n≤8，m≤8 m \leq 8 m≤8；

测试点 4 ~ 6： T=1000T = 1000 T=1000，n≤12 n \leq 12 n≤12，m≤12 m \leq 12 m≤12；

测试点 7 ~ 9： T=1000T = 1000 T=1000，n≤100 n \leq 100 n≤100，m≤100 m \leq 100 m≤100；

测试点 10 ~ 12：T=1000 T = 1000 T=1000，n≤1000 n \leq 1000 n≤1000，m≤1000 m \leq 1000 m≤1000；

测试点 13 ~ 14：T=500000 T = 500000 T=500000，n≤1000 n \leq 1000 n≤1000，m≤1000 m \leq 1000 m≤1000；

测试点 15 ~ 20：T=500000 T = 500000 T=500000，n≤1000000 n \leq 1000000 n≤1000000，m≤1000000 m \leq 1000000 m≤1000000。

分析

选出哪些元素固定，剩下的就是错排问题。

错排数递推公式：

\[D_0=1,D_1=0 \\
D_n=(n-1)(D_{n-1}+D_{n-2}) \quad n\ge 2
\]

答案为

\[\binom nm D_{n-m}
\]

时间复杂度\(O(n+T)\)

代码

#include<bits/stdc++.h>

#define rg register

#define il inline

#define co const

template<class T>il T read(){

    rg T data=0,w=1;rg char ch=getchar();

    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}

    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();

    return data*w;

}

template<class T>il T read(rg T&x) {return x=read<T>();}

typedef long long ll;

co int N=1e6+1,mod=1e9+7;

int num[N]={1,1},inv[N]={1,1},f[N]={1,0};

il int mul(int x,int y){return (ll)x*y%mod;}

int main(){

//	freopen(".in","r",stdin),freopen(".out","w",stdout);

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

		num[i]=mul(num[i-1],i);

		inv[i]=mul(mod-mod/i,inv[mod%i]);

		f[i]=mul(i-1,f[i-1]+f[i-2]);

	}

	for(int i=2;i<N;++i) inv[i]=mul(inv[i-1],inv[i]);

	for(int t=read<int>(),n,m;t--;){

		read(n),read(m);

		printf("%d\n",mul(num[n],mul(inv[n-m],mul(inv[m],f[n-m]))));

	}

	return 0;

}

巴特西

LG4071 [SDOI2016]排列计数

题意

题目描述

输入输出格式

输入输出样例

说明

分析

代码

最新文章

热门文章