luogu题目传送门!

luogu博客通道!

这题要用到错排,先理解一下什么是错排:

问题:有一个数集A,里面有n个元素 a[i]。求,如果将其打乱,有多少种方法使得所有第原来的i个数a[i]不在原来的位置上。

可以简单这么理解:

数集(初始)
1

2

3

4

5

6

错排转化后(一种情况):

2

1

4

3

6

5

于是,我们设f[i]为数集中有总共i个数时,其错排的方案数有多少。 那么,经过大量的手摸, 我们来求一下递推式:

f[0] = f[2] = 1, f[1] = 0,这些是显而易见的。当i大于3以后,假设存在一个数字k,我们手摸一下n出现在第k位的情况,发现会有以下两种:

1、数字n刚好在第k位,则我们要求的就是剩下n - 2个数的错排。即f[i - 2]\ 2、数字n不在第k位,则我们要求的就是n - 1个数的错排,即f[i - 1] 又由于我们的k是属于区间[1, n)的,又有n - 1种取值。\ 所以,我们要再乘上n - 1.即为 f[i] = (i - 1) * (f[i - 1] + f[i - 2])

回归本题 。 题目翻译:求在长为n的全排列中,第i位恰好是i,且满足条件的个数刚好有m个。 如果反过来看,就是把排列中的m个数抽出来,使得剩下的n - m个数全都不在自己的位置上。

那么答案就很明显了,ans = C(n, m) * f[n - m];

代码来一波:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000010
#define isdigit(c) ((c)>='0'&&(c)<='9')
const ll mod = (int)1e9 + ; inline ll read(){
ll x = ;
char c = getchar();
while(!isdigit(c)){
c = getchar();
}
while(isdigit(c)){
x = (x << ) + (x << ) + (c ^ '');
c = getchar();
}
return x;
} ll n, m;
struct node{
ll l, r;
} t[N]; ll inv[N], fac[N];
ll maxn = , maxm = ;
ll f[N]; ll pow(ll a,ll b){//求a的 b次方
ll s = ,temp = a;
while(b){
if(b & )s = (s * temp) % mod;
temp = (temp * temp) % mod;
b >>= ;
}
return s % mod;
} inline ll C(ll n, ll m){
if(n < m) return ;
else return inv[n] * fac[m] % mod * fac[n-m] % mod;
} void prepare(){
inv[] = fac[] = ;
for(int i = ;i <= maxn;i++)
inv[i] = inv[i-] * i % mod;
fac[maxn] = pow(inv[maxn], mod - ) % mod;//费马小定理求逆元
for(int i = maxn - ; i;i--)
fac[i] = fac[i + ] * (i + ) % mod; /*以上均是组合数求解*/
f[] = , f[] = , f[] = ;
for(int i = ;i <= maxn; i++){
f[i] = ((i - ) * (f[i - ] + f[i - ] % mod)) % mod; /*错排处理*/
}
return ;
} int main(){
ll T = read();
for(int i = ;i <= T; i++){
n = read(), m = read();
t[i] = (node){n, m};
maxn = max(maxn, n);/*先找最大值可以降低某些点的复杂度*/
}
prepare();
for(int i = ;i <= T; i++){
printf("%lld\n", C(t[i].l, t[i].r) * f[t[i].l - t[i].r] % mod); }
return ;
}

最新文章

  1. 记SpannableString设多少span时注意事项
  2. 可视化工具gephi源码探秘(二)---导入netbeans
  3. 标准MDL方法修改Page、NonPage内存的属性
  4. 职业操盘手内部教材 z
  5. 使用maphilight高亮显示map的指定area
  6. 远程控制编写之屏幕传输 MFC实现 屏幕截图 发送bmp数据 显示bmp图像
  7. vim实用笔记
  8. 【TEGer 在全球架构师峰会】 : 腾讯海外计费系统架构演进
  9. iOS 11: CORE ML—浅析
  10. for循环增强
  11. Python基础语法(三)
  12. c3p0 操作
  13. (一)flutter第一天
  14. QT,QT SDK, QT Creator 区别
  15. [转]mysql dual虚拟表
  16. js用img代替ajax js心跳 向服务器定时传送参数 主要计算用户在线时长
  17. Shell输入输出重定向
  18. Jquery解析json数组字符串
  19. Java虚拟机(一)之开篇
  20. 很小的一个函数执行时间调试器Timer

热门文章

  1. 记一次真实的线上事故:一个update引发的惨案!
  2. MySQL 入门(2):索引
  3. .NET Core技术研究-通过Roslyn代码分析技术规范提升代码质量
  4. Shell脚本(五)函数
  5. 学习Vue第一节,Vue的模式与写法格式
  6. 搬东西 dp
  7. 201771010113 李婷华 《面向对象程序设计(Java)》第八周总结
  8. 【不断更新】mysql经典50道题自我练习
  9. scala 隐式参数
  10. 小程序-for循环遍历的使用