首页 > 代码库 > 【bzoj4517】[Sdoi2016]排列计数 组合数+乘法逆元+dp
【bzoj4517】[Sdoi2016]排列计数 组合数+乘法逆元+dp
题目描述
求有多少种长度为 n 的序列 A，满足以下条件：
1 ~ n 这 n 个数在序列中各出现了一次
若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的
满足条件的序列可能很多，序列数对 10^9+7 取模。
输入
第一行一个数 T，表示有 T 组数据。
接下来 T 行，每行两个整数 n、m。
T=500000，n≤1000000，m≤1000000
输出
输出 T 行，每行一个数，表示求出的序列数
样例输入
5
1 0
1 1
5 2
100 50
10000 5000
样例输出
0
1
20
578028887
60695423
题解
组合数+乘法逆元+dp
题目中说n个数有m个稳定的，有n-m个不稳定的，那么我们可以从这n个数中选出m个作为稳定的数，其余的n-m个作为不稳定的数。
n选m需要用到组合数，然而n和m太大不能递推来求。
考虑到C(n,m)=n!/(m!(n-m)!)，我们可以先预处理阶乘模MOD的值，再用乘法逆元。
而这里的MOD为质数，根据费马小定理，ap≡a(mod p)，即ap-1≡1(mod p)，即a*ap-2≡1(mod p)，即1/a≡ap-2(mod p)
所以直接用快速幂求aMOD-2就是乘法逆元。
然后是n-m个不稳定的，即错排，dp公式：f[n]=(n-1)*(f[n-1]+f[n-2])
解释：第n个物品有n-1个位置可选，假设选定了k位置，考虑k的选择分两种，不选n和选n。不选n的情况，将n看作k，即k不能选择自身，转化为f[n-1]；选N的情况即f[n-2]。
乘起来模上MOD即可。
#include <cstdio>
#define N 1000010
#define MOD 1000000007
typedef long long ll;
ll fac[N] , f[N];
ll qpow(ll x , int y)
{
ll ans = 1;
while(y)
{
if(y & 1) ans = (ans * x) % MOD;
x = (x * x) % MOD , y >>= 1;
}
return ans;
}
int main()
{
int i , T , n , m;
fac[0] = 1;
for(i = 1 ; i <= 1000000 ; i ++ ) fac[i] = fac[i - 1] * i % MOD;
f[0] = 1 , f[1] = 0;
for(i = 2 ; i <= 1000000 ; i ++ ) f[i] = (i - 1) * (f[i - 1] + f[i - 2]) % MOD;
scanf("%d" , &T);
while(T -- )
{
scanf("%d%d" , &n , &m);
printf("%lld\n" , qpow(fac[m] , MOD - 2) * qpow(fac[n - m] , MOD - 2) % MOD * fac[n] % MOD * f[n - m] % MOD);
}
return 0;
}
【bzoj4517】[Sdoi2016]排列计数 组合数+乘法逆元+dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。