题解 P4071 【[SDOI2016]排列计数】

那么这道题是一个非常棒的错排问题的入门题 对于这类求方案数的问题的话 关键是不重不漏……，对于这道题可以使用枚举“区分点”的方法 也就是说，我们枚举的“区分点”，必须要让任意两个方案，只要区分点不同，那么这两个方案就不同 那么对于这道题来讲，就是如果连稳定的数字都不一样了，这两个方案就肯定不同了，那这样的话，那些数字是稳定的就是所谓的区分点所以我们可以先钦定到底哪m个数是稳定的，一共有$C_{n}^{m}$种方案 下面在钦定了这m个数字稳定之后，其他的数字必须全部不稳定，这个问题被称为全错排问题，也就是说，没有一个数字是稳定的序列个数 设$D_{n}$为长度为n的全错排序列个数那么的话我们呢会有一个一个递推式子 假设我们现在要求长度为n的错排方案数 那么我们呢就枚举第n个位置放在那个位置数上 显然一共有n-1个位置可以放，并且肯定有一个数t放在了第n个位置上 假设n放在了t位置上，那么剩下的序列必须构成一个长度为n-2的错排列 假设n没有放在t位置上，那么剩下的序列必须构成一个长度为n-1的错排列(因为n不能放在t上了) 上述两种情况是互斥的，因此可以直接加起来 枚举n放在那个位置是独立的，因此可以和上述两种情况乘起来 因此我们就有了一个极吼的递推公式 $D_{n}=(n-1)(D_{n-1}+D_{n-2})$ 然后我们最后输出$C_{n}^{m}×D_{n-m}$就好啦 关于求组合数的问题可以打表逆元和阶乘，然后我们就可以$O(10^{6})$预处理 然后$O(1)$回答询问啦~ 上代码~ ```C #include<cstdio> #include<algorithm> using namespace std;const int N=1e6+10;typedef long long ll; const ll mod=1e9+7;ll inv[N];ll fac[N];ll ifac[N];ll d[N];int T;int n;int m; int main() { inv[1]=1;for(int i=2;i<=N-10;i++){inv[i]=(mod-mod/i)*inv[mod%i]%mod;}//打标逆元 fac[0]=1;for(int i=1;i<=N-10;i++){fac[i]=fac[i-1]*i%mod;}//打表阶乘 ifac[0]=1;for(int i=1;i<=N-10;i++){ifac[i]=ifac[i-1]*inv[i]%mod;}//打表逆元和阶乘 d[0]=1;d[1]=0;d[2]=1;for(ll i=3;i<=N-10;i++){d[i]=(i-1)*(d[i-1]+d[i-2])%mod;}//打表错排 scanf("%d",&T); for(int i=1;i<=T;i++) { scanf("%d%d",&n,&m); printf("%lld\n",fac[n]*ifac[m]%mod*ifac[n-m]%mod*d[n-m]%mod);//输出答案 }return 0;//拜拜程序~ } ```