P4071 - SDOI2016 - D2T1 - 排列计数#

题目信息#

难度：提高+/省选-

算法：数学递推，逆元

题目描述#

求有多少种 $1$ 到 $n$ 的排列 $a$，满足序列恰好有 $m$ 个位置 $i$，使得 $a_i=i$.

答案对 $10^9+7$ 取模，多组询问，询问次数为 $T$.

对于 $100\%$ 的数据，$0\leq m\leq 10^6$.

$\rm{Subtask}$ $\rm{1}$#

$T=10^3$，$n, m\leq 8$.

对于每次询问，暴力枚举所有排列，时间复杂度 $\mathcal{O}(T\times n!)$，期望得分 $\rm{15pts}$.

$\rm{Subtask}$ $\rm{2}$#

想到错排之后，正解非常自然。

根据小学排列组合知识，我们从数列中任意取 $n$ 个数，让它们满足 $a_i=i$，情况数为 $C_{n}^{m}$.

又因为 $n$ 个数的排列中，有 $m$ 个位置满足 $a_i=i$，对于剩下的 $n-m$ 个位置需要满足 $a_i\neq i$.

这样的情况数是 $n-m$ 的错排数，也就是 $D_{n-m}$.

由于乘法原理，最终的答案就是 $C_{n}^m\times D_{n-m}$.

对于多组询问，我们需要 $\mathcal{O}(n)$ 预处理组合数和错排数。

错排#

概念#

对于一个 $n$ 个元素的排列，若一个排列中所有的元素都不在自己的位置上，这样的一个排列称为一个错排。

一般将 $n$ 个元素的错排数量记作 $D_n$.

通过递推，可以在 $\mathcal{O}(n)$ 的复杂度内处理出 $D_1,D_2\cdots, D_n$.

递推式#

推导过程不唯一。

第一步，在 $[1, n-1]$ 中任取一个元素 $i$，将 $n$ 连向 $i$，方法数量为 $(n-1)$.

第二步，确定 $i$ 连向哪个元素，分类讨论：

1. $i$ 连向 $n$.

   此时剩下的 $n-2$ 个元素要满足错排，对答案贡献为 $(n-1)\times D_{n-2}$.

2. $i$ 不连向 $n$.

   此时，相当于有 $n-1$ 个元素需要满足错排，对答案贡献为 $(n-1)\times D_{n-1}$.

   根据加法原理，得到递推式：

​ 特殊地，$D_1=0$，$D_2=1$.

求逆元 & 组合数#

扩展欧几里得#

概述#

扩展欧几里得算法是用来在已知 $a,b$ 的情况下求解一组 $x,y$，使满足 $ax+by=gcd(a,\,b)=d$.

$\gcd(a, b)$ 为 $a, b$ 的最大公因数，方程一定有整数解。

特解#

要计算 $\gcd(a,\,b)$，并求出满足条件的 $x,y$.

将下一个状态 $b$ 和 $(a\%b)$ 表示为：$b\cdot x_1+(a\%b)\cdot y_1=d$

则：

所以满足条件的 $x=y_1,\,y=x_1-\left\lfloor\frac{a}{b}\right\rfloor\times y_1$.

int exgcd(int a, int b, int &x, int &y) {//函数返回值为gcd(a,b)
    if(b == 0) {
        x = 1;//gcd(a,b) = a = 1a+0b
        y = 0;
        return a;
    }
    int r = exgcd(b, a % b, x, y);//先递归
    int t = x;//再计算x,y
    x = y;
    y = t - a / b * y;
    return r;
}

时间复杂度为：$\mathcal{O}(\min(\log a, \log b))$，即 $\mathcal{O}(\log n)$ 级别。

通解#

假设特解为 $(x_0,y_0)$，满足 $ax_0+by_0=gcd(a,\,b)=d$，

则有：

所以方程的通解为：

对于其它二元一次不定方程$ax+by=c$（$c$为任意正整数）只有当 $d\mid c$ 时才有整数解，通解形式：

同余方程（模方程）#

概述#

指形如 $ax\equiv b\pmod c$ 的一种方程。其中 $a,b,c$ 是参数，$a,c$ 是正整数，$b$ 是小于 $c$ 的非负整数，$x$ 是未知数。

解同余方程#

根据同余定义，$ax\equiv b\pmod c$ 可化为 $xa+kc=b$. 其中 $a,b,c$ 已知，$x,k$ 未知，所以能用扩展欧几里得解同余方程。

通解#

如果 $b\nmid gcd(a,c)$，方程无整数解.

否则同扩展欧几里得酸法，求得通解：

其中 $k\in \Bbb{Z}$.

最小非负整数解#

因为 $x=\frac{b}{d}x_0+k\frac{c}{d}$，其中 $x_0$ 是方程 $xa+kc=gcd(a,\,c)$ 的特解， $\frac{b}{d}x_0$ 是原同余方程的特解，

若 $x>0$，则有 $x\equiv \frac{b}{d}x_0 \pmod{ \frac{c}{d}}$。最小非负整数解为 $\frac{b}{d}x_0\,\%\,\frac{c}{d}$.

若 $x<0$，同理，最小非负整数解为 $(\frac{b}{d}x_0\bmod \frac{c}{d}+\frac{c}{d} )\bmod\frac{c}{d}$.

综上，最小非负整数解为：

乘法逆元#

概述#

给定两个整数 $a$ 和 $p$，假设存在 $x$ 使得 $ax\equiv 1\pmod p)$，称 $x$ 为 $a$ 关于 $p$ 的乘法逆元。

$a$ 关于 $p$ 的逆元存在的充分必要条件是 $\gcd(a,p)=1$.

在模意义下，乘一个数 $x$ 的逆元，可以理解为除以 $x$.

求一个数的逆元#

将上面式子变形，变成 $ax+kp=1$，用扩展欧几里得能够求出一个 $x$.

如果 $p$ 是质数，有另一种方法求 $a$ 关于 $p$ 的逆元（费马小定理）

所以 $a$ 关于 $p$ 的逆元是 $a^{b-2}\bmod b$ 的值，用快速幂优化。

时间复杂度：均为 $\mathcal{O}(\log n)$ 级别。

线性预处理逆元#

在 $\mathcal{O}(n)$ 的时间复杂度内，求出任意 $n$ 个数的逆元，一般用于处理 $1\sim n$ 的逆元。

设我们要处理出 $a_1, a_2\cdots, a_n$ 的逆元。

第一步，预处理出前缀积数组 $\operatorname{pre}_i=\prod_{j=1}^ia_i$.

第二步，求出 $\operatorname{pre}_n$ 的逆元 $\operatorname{pre\_inv}_n$，复杂度 $\mathcal{O}(\log n)$.

第三步，通过 $\operatorname{pre\_inv}_i$，求出 $\operatorname{pre\_inv}_{i-1}$.

在模意义下，$\operatorname{pre\_inv}_i=\frac{1}{a_1\times a_{2}\times \cdots \times a_{i}}$，$\operatorname{pre\_inv}_{i-1}=\frac{1}{a_1\times a_2\times\cdots\times a_{i-1}}=\operatorname{pre\_inv}_{i}\times a_i$.

第四步，通过 $\operatorname{pre\_inv}_i$，求出 $\operatorname{inv}_i$.

在模意义下，$\operatorname{inv}_i=\operatorname{pre}_{i-1}\times \operatorname{pre\_inv}_{i}$.

在上面的步骤中，$\operatorname{pre\_inv}_i$ 即为 $i$ 的阶乘的逆元，在处理组合数时常用。

有另一种方法也可以处理逆元，时间复杂度相同，但不好记，而且证明麻烦，不需要掌握。

inv[1] = 1;
for (int i = 2; i <= n; ++i) {
    inv[i] = (p - p / i) * inv[p % i] % p;
}

预处理组合数#

预处理后，$\mathcal{O}(1)$ 地求解 $[1, n]$ 范围内的组合数，对大质数取模的结果。

记 $\operatorname{fac}_n=n!$，根据组合数的定义式：

可以得到：

所以预处理出 $[1, n]$ 的阶乘，以及阶乘的逆元，每次即可 $\mathcal{O}(1)$ 求组合数。

int fac[], inv_fac[];
fac[0] = 1;
for(int i = 1; i <= n; i++)
	fac[i] = fac[i - 1] * i % p;
inv_fac[n] = power(fac[n], p - 1);
for(int i = n - 1; i >= 0; i--)
	inv_fac[i] = inv_fac[i + 1] * (i + 1) % p;

P4343 - SHOI2015 - 自动刷题机#

题目信息#

难度：提高+/省选-

算法：二分答案

题目描述#

自动刷题机刷题的方式非常简单：首先会瞬间得出题目的正确做法，然后开始写程序。每秒，自动刷题机的代码生成模块会有两种可能的结果：

1. 写了 $x$ 行代码
2. 心情不好，删掉了之前写的 $y$ 行代码。（如果 $y$ 大于当前代码长度则相当于全部删除。）

对于一个 OJ，存在某个固定的正整数长度 $n$，一旦自动刷题机在某秒结束时积累了大于等于 $n$ 行的代码，它就会自动提交并 AC 此题，然后新建一个文件（即弃置之前的所有代码）并开始写下一题。SHTSC 在某个 OJ 上跑了一天的自动刷题机，得到了很多条关于写代码的日志信息。他突然发现自己没有记录这个 OJ 的 $n$ 究竟是多少。所幸他通过自己在 OJ 上的 Rank 知道了自动刷题机一共切了 $k$ 道题，希望你计算 $n$ 可能的最小值和最大值。

题目给定 $l$ 条刷题日志，每条有一个整数 $x_i$ 表示添加的代码行数。

$1\leq l\leq 10^5, -10^9\leq x_i\leq 10^9$.