洛谷P4071-[SDOI2016]排列计数 题解

2020-01-12 16:01:34来源:博客园 阅读 ()

容器云强势上线!快速搭建集群,上万Linux镜像随意使用

洛谷P4071-[SDOI2016]排列计数 题解

SDOI2016-排列计数

发现很多题解都没有讲清楚这道题为什么要用逆元、递推公式怎么来的。 我,风雨兼程三十载,只为写出一篇好题解。 还是我来造福大家一下吧。

题目大意:

一个长度为 n 且 1~n 各出现一次的序列,希望在“序列中有且只有 m个数的值 等于 它的位置”条件下求出序列个数。答案对1000000007取模。

题目分析:

这道题也许是加强版的“装错了的信封”,在“装错了的信封”上搞搞比利就好。我们不妨设:
值等于位置的数字稳定的
值不等于位置数字不稳定的

稳定的数字由于要保证 值等于位置,故 稳定的数字从序列左到右的值是递增的

首先我们根据组合数的思想可以知道:

答案 = 稳定的挑选方法数 乘上 不稳定的挑选方法数

所以现在我们的目的改成了求出 稳定的挑选方法数不稳定的挑选方法数

稳定的挑选方法数:

我们已经知道了 稳定的数字从序列左到右的值是递增的,那么我们只需要模拟是哪几个数是稳定的即可。

不难想到,数量其实就是 在 n 个数中 挑选 m 个数的方案数

这不就是组合数里面的 \(C_n^m\) 吗?有 \(C_n^m\) = \(\frac{n!}{m!(n-m)!}\)

搞定

不稳定挑选方法数(错排):

我们假设已经知道了哪 m 个数是稳定的,那么我们可以在数组中暂时只看不稳定的数。

也就是 错排

我们令数组 \(F_x\)有 x 个数字,每个数字均为不稳定的方法数

由于这些数是不稳定的,那么就没有值的大小递增关系,所以我们对于每一个 \(F_x\) ,都要进行分类讨论。

\[假设一个数字 k ,并令 n 位于第 k 位: \begin{cases} 当 k 位于第n位& \text{此时的错排数为 $F_{n-2}$(因 k 的位置已确定,即求剩下的 n-2 个数的错排数)}\\ 当 k 不位于第n位& \text{此时的错排数为 $F_{n-1}$} \end{cases}\]

于是对于每个 \(F_i\) ,有 \(F_i\) = (i - 1) × (\(F_{x-1}\) + \(F_{x-2}\))

所以最终答案为:(\(C_n^m \times\)\(F_{n-m}\))%MOD

具体操作思路:

我们先要初始化,对于 \(C_x^y\) 要初始化阶乘,对于 \(F_i\) 要递推。

然后对于每一组数据,套 (\(C_n^m \times\)\(F_{n-m}\))%MOD 即可。

但是(还没完):

由题意得,最终方案数可能很大(所以才要取模),我们在进行 答案累乘时,(\(C_n^m \times\)\(F_{n-m}\))%MOD 可能会爆精度,我们于是要用到:

逆元(inv)

何为逆元(inv)?

比如当有 (a/b)%MOD 时,防止 b 过大而爆精度,将 a/b 转化为某种简单的乘法。

若 c 为 b 的逆元,则有 (b * c) ≡ 1 (mod 模数)

那么 (a/b)%mod = (a/b)1%mod = (a/b)bc%mod = (ac)%mod

即 (一个数 除以 另一个数)%模数 = (一个数 乘上 另一个数的逆元)%模数

如何将逆元应用到该题中

我们初始化逆元数组 inv ,inv 为 阶乘的逆元

那对于固定的值于模数,那个值的逆元怎么求呢?

请你参考费马小定理

直接给出答案:对于 a % 1000000007 的逆元,为 \(a^{1000000007-2}\)

搞个快速幂就好了

代码:

#include<bits/stdc++.h>
#include<cctype>
#pragma GCC optimize(2)
#define Max(a,f) a > b ? a : b
#define Min(a,b) a < b ? a : b
#define in(n) n = read()
#define out(a) write(a)
#define outn(a) out(a),putchar('\n')
#define New ll
#define ll long long
#define rg register
using namespace std;

namespace IO_Optimization//优化函数 
{
    inline New read()//快读 
    {
        New X = 0,w = 0;
        char ch = 0;

        while(!isdigit(ch))
        {
            w |= ch == '-';
            ch=getchar();
        }
        while(isdigit(ch))
        {
            X = (X << 3) + (X << 1) + (ch ^ 48);
            ch = getchar();
        }
        return w ? -X : X;
    }

    inline void write(New x)//快输 
    {
         if(x < 0) putchar('-'),x = -x;
         if(x > 9) write(x / 10);
         putchar(x % 10 + '0');
    }
}
using namespace IO_Optimization;

const int mod = 1000000000 + 7;//模数 
const int MAXN = 1000000 + 2;//数组大小常量 

ll a[MAXN],f[MAXN],inv[MAXN];
// 阶乘    F数组   逆元数组 

inline ll ksm(ll a,ll b){//快速幂函数,求逆元 
    ll ans = 1;
    a %= mod;
    while(b)
    {
        if(b & 1)
            ans = (a * ans) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

int main()
{
    a[0] = 1;//初始化 
    for(rg int i = 1;i <= MAXN; ++i)
    {
        a[i] = (a[i - 1] * i) % mod;//记得取模 
        inv[i] = ksm(a[i],mod - 2);//计算逆元 
    }
    f[1] = 0,f[2] = 1,f[3] = 2;//初始化 
    for(rg int i = 4;i <= MAXN; ++i)
        f[i] = ((i - 1) * (f[i - 1] + f[i - 2])) % mod;//递推公式 
    int T = read();//多数据输入 
    while(T--)
    {
        int n = read(),m = read(),k = n - m;//输入n、m,k纯属方便 
        if(!k)//如果n-m=0,那么方案数为1 
        {
            puts("1");
            continue;
        }
        if(m == 0)//如果没有稳定的数,那么答案直接等于F[n] 
        {
            outn(f[n]);
            continue;
        }
        if(k == 1)//如果n-m=1,则有0个方案 
        {
            puts("0");
            continue;
        }
        outn(((( a[n] * inv[k] ) % mod * inv[m]) % mod * f[k]) % mod);//输出
        //上面是把除法改成乘法逆元了 
    }
    return 0;
}

原文链接:https://www.cnblogs.com/CJYBlog/p/permutation.html
如有疑问请与原作者联系

标签:git操作函数extfor方法

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:条款03:尽可能使用const

下一篇:结题报告