【题解】排列计数
题目描述
求有多少种 1 到 n 的排列 a，满足序列恰好有 m 个位置 i，使得
。
答案对
取模。
输入格式
本题单测试点内有多组数据。
输入的第一行是一个整数 T，代表测试数据的整数。
以下 T 行，每行描述一组测试数据。
对于每组测试数据，每行输入两个整数，依次代表 n 和 m。
输出格式
共输出 T 行，对于每组测试数据，输出一行一个整数代表答案。
输入输出样例
输入 #1
5
1 0
1 1
5 2
100 50
10000 5000输出 #1
0
1
20
578028887
60695423说明/提示
数据规模与约定
本题共 20 个测试点，各测试点等分，其数据规模如下表。
测试点编号 | T = | n,m≤n, m \leqn,m≤ | 测试点编号 | T = | n,m≤n, m \leqn,m≤ |
|---|---|---|---|---|---|
1∼31\sim 31∼3 | 10310^3103 | 8 | 10∼1210 \sim 1210∼12 | 10310^3103 | 10310^3103 |
4∼64 \sim 64∼6 | 10310^3103 | 12 | 13∼1413 \sim 1413∼14 | 5×1055 \times 10^55×105 | 10310^3103 |
7∼97 \sim 97∼9 | 10310^3103 | 100 | 15∼2015 \sim 2015∼20 | 5×1055 \times 10^55×105 | 10610^6106 |
对于全部的测试点，保证
题目分析
不了解错排的同学可以先了解下错排。
可发现该问题是错排的一个变形。题目要求的是有"m 个位置 i，使得 ai=ia_i = iai=i。"。相当于从n个数中，挑m个位置不变动，剩下的进行错排。
就可得到计算公式：
本题中n,m的范围很大，首先利用同余性质，预处理求出阶乘、错排列取余后的内容。再利用乘法逆元，将a/b转成
，再利用同余性质进行处理。
逆元则可利用费马小定理进行求解：
此时逆元x可取为
预处理
jc[0]=1;jc[1]=1,jc[2]=2;
d[0]=0;d[1]=0;d[2]=1;
for(int i=3;i<=N-5;i++){
d[i]=(i-1)*(d[i-2]+d[i-1])%M;
jc[i]=jc[i-1]*i%M;
}快速幂
ll mypow(ll x,ll n,int M){
if(n==0) return 1%M;
ll tmp=mypow(x,n/2,M)%M;
if(n&1) return tmp*tmp%M*x%M;
else return tmp*tmp%M;
}代码实现
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int M=1e9+7;
const int N=1e6+5;
ll mypow(ll x,ll n){//快速幂 求 x的n次幂
if(n==0) return 1%M;
ll tmp=mypow(x,n/2)%M;
if(n&1) return tmp*tmp%M*x%M;
else return tmp*tmp%M;
}
ll jc[N];//jc[x] = x!
ll d[N];//d[x] = x个元素的错排列数
ll C(int n,int m){//求组合C(n,m)
return jc[n]*mypow(jc[m]*jc[n-m]%M,M-2)%M;
}
int main(){
int t,n,m;
scanf("%d",&t);
//预处理 阶乘 和 错排列数
jc[0]=1;jc[1]=1,jc[2]=2;
d[0]=0;d[1]=0;d[2]=1;
for(int i=3;i<=N-5;i++){
d[i]=(i-1)*(d[i-2]+d[i-1])%M;
jc[i]=jc[i-1]*i%M;
}
while(t--){
scanf("%d%d",&n,&m);
if(n==m) printf("1\n");
//C(n,m)*D(n-m)
else printf("%lld\n",C(n,m)*d[n-m]%M);
}
return 0;
}
Q.E.D.
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录