【SDOI 2016】排列计数

【题目链接】

https://www.lydsy.com/JudgeOnline/problem.php?id=4517

【算法】

有m个数在原来的位置上，说明有(n-m)个数不再原来的位置上

那么，我们可以选出(n-m)个数，使这(n-m)个数都不在原来的位置上，再让剩下的m个数都在原来的位置上

错位排列递推公式：

f(1) = 0

f(2) = 1

f(n) = (n - 1)(f(n-1) + f(n-2)) (n >= 2)

因此，答案为C(n,n-m)f(n-m)

预处理错位排列数，阶乘和阶乘逆元，即可

【代码】

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000010
const int P = 1e9 + 7;

int T,n,m,ans;
int f[MAXN],fac[MAXN],inv[MAXN];

inline int power(int a,int n)
{
        int res = 1,b = a;
        while (n)
        {
                if (n & 1) res = 1ll * res * b % P;
                b = 1ll * b * b % P;
                n >>= 1;
        }
        return res;
}
inline void init()
{
        int i;
        f[0] = 1;
        f[1] = 0;
        f[2] = 1;
        for (i = 3; i < MAXN; i++) f[i] = 1ll * (i - 1) * (f[i-1] + f[i-2]) % P;
        fac[0] = 1;
        for (i = 1; i < MAXN; i++) fac[i] = 1ll * fac[i-1] * i % P;
        inv[MAXN-1] = power(fac[MAXN-1],P-2);
        for (i = MAXN - 2; i >= 0; i--) inv[i] = 1ll * inv[i+1] * (i + 1) % P;
}
inline int C(int n,int m)
{
        if (n < m) return 0;
        if (m == 0) return 1;
        return 1ll * fac[n] * inv[m] % P * inv[n-m] % P;        
}

int main() 
{
        
        init();
        scanf("%d",&T);
        while (T--)
        {
                scanf("%d%d",&n,&m);
                ans = 1ll * C(n,n-m) * f[n-m] % P;
                printf("%d
",ans);                        
        }
        
        return 0
    
}

【SDOI 2016】 排列计数

相关推荐

【SDOI 2016】排列计数