洛谷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)\times(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 \div b) \% MOD$ 时，防止 $b$ 过大而爆精度，将 $a \div b$ 转化为某种简单的乘法。

若 $c$ 为 $b$ 的逆元，则有 $(b \times c) \equiv 1 (mod 模数)$

那么 $(a \div b) \% MOD$ = $(a \div b) \times 1 \% MOD$ = $(a \div b) \times b \times c \% MOD$ = $(a \times c) \% 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;

}

巴特西

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

题目大意：

题目分析：

稳定的挑选方法数：

不稳定挑选方法数（错排）：

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

具体操作思路：

如何将逆元应用到该题中

代码：

最新文章

热门文章

巴特西

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

题目大意：

题目分析：

稳定的挑选方法数：

不稳定挑选方法数（错排）：

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

具体操作思路：

如何将逆元应用到该题中

代码：

最新文章

热门文章

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