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

HINT

Source

鸣谢Menci上传

啊啊为什么我这么菜QWQ。。

这题一个公式就过去了,

考虑一个数i,只有当i在第i个位置时才能产生贡献,

那么需要产生m个数的方案就是C_n^m

然后让剩下的数错排,设错排的方案数为D(i)

递推公式D[i]=(i-1)*D(i-1)*D(i-2)

证明:

#include<cstdio>
#define int long long 
using namespace std;
const int mod=1e9+7;
const int MAXN=1e6+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int fac[MAXN],D[MAXN],inv[MAXN];
void Pre()
{
    fac[0]=fac[1]=inv[0]=inv[1]=D[0]=D[2]=1;
    for(int i=2;i<=1000001;i++) fac[i]=(i*fac[i-1])%mod;
    for(int i=2;i<=1000001;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(int i=2;i<=1000001;i++) inv[i]=(inv[i]*inv[i-1])%mod;
    for(int i=3;i<=1000001;i++) D[i]=((i-1)*(D[i-1]+D[i-2]))%mod;
}
int Query(int N,int M)
{
    return fac[N] %mod * inv[ N-M  ] %mod * inv[ M ] %mod * D[N-M] %mod;
}
main()
{
    Pre();
    int T=read();
    while(T--)
    {
        int N=read(),M=read();
        printf("%lld\n",Query(N,M)%mod);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据挖掘DT机器学习

python数据分析师面试题选

python数据分析部分 1. 如何利用SciKit包训练一个简单的线性回归模型 利用linear_model.LinearRegression()函数 #...

6296
来自专栏数据魔术师

运筹学教学 | 十分钟教你求解分配问题(assignment problem)

biu~ biu~ biu~ 我们的运筹学教学推文又出新文拉 还是熟悉的配方,熟悉的味道 今天向大家推出的是 运筹学教学--第六弹 分配问题(Assignmen...

1.4K8
来自专栏数据结构与算法

Day4晚笔记

数据结构 并查集:捆绑两个点的信息,判断对错 倍增:LCA, 字符串 hash,模拟, 最小表示法 给定一个环状字符串,切开,使得字符串的字典序最小 图和树 割...

2644
来自专栏软件开发 -- 分享 互助 成长

经典算法学习之回溯法

回溯法的应用范围:只要能把待求解的问题分成不太多的步骤,每个步骤又只有不太多的选择就可以考虑使用回溯法。  若用回溯法求问题的所有解时,要回溯到根,且根结点的所...

2388
来自专栏DannyHoo的专栏

iOS开发中使用算法之冒泡法

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u010105969/article/details/...

1153
来自专栏蜉蝣禅修之道

优化后的Levensthein distance算法实现

3885
来自专栏数据结构与算法

2-SAT速成

本文只做总结性说明 2-SAT 2-SAT是k-SAT问题的一种,k-SAT问题在k>=3时已经被证明是NP完全问题 2-SAT问题定义比较简单 有n个布尔变量...

2856
来自专栏算法channel

图算法|Prim算法求最小生成树

01 — 一个实际问题 要在n个城市之间铺设光缆,要求有2个: 这 n 个城市的任意两个之间都可以通信; 铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,...

9637
来自专栏小樱的经验随笔

从零基础学三分查找

今晚是我们学长第二次讲课,讲了一个三分!认真听了一下,感觉不是很难,可能会比二分还简单些!我就把上课讲的内容归纳为一篇文章概述吧!以后也会重点讲解的! 简单点说...

44310
来自专栏ml

cf------(round)#1 C. Ancient Berland Circus(几何)

C. Ancient Berland Circus time limit per test 2 seconds memory limit per test ...

2533

扫码关注云+社区

领取腾讯云代金券