排列计数(bzoj 4517)
2024-09-08 11:24:20
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
1 0
1 1
5 2
100 50
10000 5000
Sample Output
0
1
20
578028887
60695423
1
20
578028887
60695423
/*
很容易就推出公式:ans=C(n,m)*dp[n-m]
dp[i]表示i的全错排方案数,dp[i]=(i-1)*(dp[i-1]+dp[i-2])
预处理出阶乘,阶乘的逆元和dp数组。
*/
#include<cstdio>
#include<iostream>
#define N 1000010
#define lon long long
#define mod 1000000007
#ifdef unix
#define LL "%lld"
#else
#define LL "%I64d"
#endif
using namespace std;
lon dp[N],inv[N],jc1[N],jc2[N],n,m;
void init(){
dp[]=;dp[]=;dp[]=;
for(int i=;i<N;i++)
dp[i]=(i-)*(dp[i-]+dp[i-])%mod;
inv[]=;
for(int i=;i<N;i++)
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
jc1[]=;
for(int i=;i<N;i++)
jc1[i]=jc1[i-]*i%mod;
jc2[]=;
for(int i=;i<N;i++)
jc2[i]=jc2[i-]*inv[i]%mod;
}
int main(){
init();
int T;scanf("%d",&T);
while(T--){
scanf(LL LL,&n,&m);
lon ans=jc1[n]*jc2[m]%mod*jc2[n-m]%mod*dp[n-m]%mod;
printf(LL,ans);printf("\n");
}
return ;
}
最新文章
- python_way day16 DOM
- POJ_3083——贴左右墙DFS,最短路径BFS
- Ubuntu中apt-get出现E:Encountered a section with no Package: header&hellip;&hellip;的解决方案
- Linux安装配置VPN服务器
- 快速排序OC、Swift版源码
- TC358743XBG:HDMI转MIPI CSI参考设计
- 存储引擎和表的操作(mysql中的数据类型、完整性约束)
- 浅析mysql中exists 与 in 的使用
- JavaScript的 sourcemap 的理解
- mysql windows 5.7 安装版下载地址
- python基础回顾
- C++_友元函数总结(转)
- 【DeepLearning】UFLDL tutorial错误记录
- 移动端1px细线解决方案总结
- C#常用插件和工具
- JAVA基础之sql模糊匹配、外键以及jsp中include的用法
- Macbook pro 13"; Installs Ubuntu 18.04
- AngularJS Injector和Service的工作机制
- BZOJ4975: [Lydsy1708月赛]区间翻转( 博弈&;逆序对)
- Java应用多机器部署定时任务解决方案