洛谷 P4071 [SDOI2016]排列计数

Bertha 。 2022-01-12 13:33 183阅读 0赞

![1596060-20190612191650302-584562041.png][]

![1596060-20190612191710278-1020740109.png][]

![1596060-20190612191723104-121829082.png][]

首先一看应该是组合数的问题，但我们选出m个数之后，其他的数就不能再排在它原本的位置，所以又需要错排求出方案数。

错牌公式递推式:

有***d\[2\]=1,d\[0\]=1,d\[1\]=0。d\[i\]=(i-1)\*(d\[i-1\]+d\[i-2\])***

又由乘法原理可得出总方案数。

注意：阶乘，逆元，错排都要预处理出来，否则T到飞起。

![1596060-20190612192317883-870705979.png][]

未预处理代码：

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+7;
    int T;
    long long n,m;
    long long d[maxn];
    const int mod=1e9+7;
    long long ksm(long long a,long long b){
        long long base=1;
        while(b){
            if(b&1) base=base*a%mod;
            b>>=1;
            a=a*a%mod;
        }
        return base;
    }
    long long C(long long n,long long m){
        if(n<m) return 0;
        long long a=1,b=1;
        for(long long i=n-m+1;i<=n;i++){
            a=a*i%mod;
        }
        for(long long i=1;i<=m;i++){
            b=b*i%mod;
        }    
        return a*ksm(b,mod-2)%mod;
    }
    void cp(){
        d[0]=1;
        d[2]=1;
        for(int i=3;i<=1000000;i++){
            d[i]=(i-1)*(d[i-1]+d[i-2])%mod;
        }
    }
    int main(){
        scanf("%d",&T);
        cp();
        while(T--){
            scanf("%lld%lld",&n,&m);
            printf("%lld\n",C(n,m)*d[n-m]%mod);
        }
        return 0;
    }

预处理过后：

![1596060-20190612192432610-2028134899.png][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+7;
    int T;
    long long n,m;
    long long d[maxn];
    long long inv[maxn];
    long long f[maxn];
    const int mod=1e9+7;
    long long ksm(long long a,long long b){
        long long base=1;
        while(b){
            if(b&1) base=base*a%mod;
            b>>=1;
            a=a*a%mod;
        }
        return base;
    }
    long long C(long long n,long long m){
        if(n<m) return 0;
        long long a=1,b=1;
        for(long long i=n-m+1;i<=n;i++)    a=a*i%mod;
        for(long long i=1;i<=m;i++)    b=b*i%mod;
        return a*ksm(b,mod-2)%mod;
    }
    void cp(){
        d[0]=1;
        d[2]=1;
        for(int i=3;i<=1000000;i++)    d[i]=(i-1)*(d[i-1]+d[i-2])%mod;
    }
    void jc(){
        f[1]=1;
        f[0]=1;
        for(int i=2;i<=1000000;i++)    f[i]=f[i-1]*i%mod;
    }
    void ny(){
        inv[0]=ksm(f[0],mod-2);
        for(int i=1;i<=1000000;i++)    inv[i]=ksm(f[i],mod-2)%mod;
    }
    void work(){
        printf("%lld\n",(f[n]*inv[m]%mod*inv[n-m]%mod*d[n-m])%mod);
    }
    int main(){
        scanf("%d",&T);
        cp();
        jc();
        ny();
        while(T--){
            scanf("%lld%lld",&n,&m);
            work();
        }
        return 0;
    }

转载于:https://www.cnblogs.com/LJB666/p/11011705.html

[1596060-20190612191650302-584562041.png]: /images/20220109/3e1eab5edd2a4d6c987ea48df6b52dc1.png
[1596060-20190612191710278-1020740109.png]: /images/20220109/ce441b02ab8144eb9403057a2d4b3703.png
[1596060-20190612191723104-121829082.png]: /images/20220109/1cfc4219ba1c4727b94c39a8975f7ade.png
[1596060-20190612192317883-870705979.png]: /images/20220109/abc246e53f924b22ab0e4b4514a069c6.png
[1596060-20190612192432610-2028134899.png]: /images/20220109/7dba1f64a2f74b678e3ca8195347135b.png