二分和分治&数学基础(二) —— 跟WilliamYan一起学算法

这里是《跟WilliamYan一起学算法》!
因为二分和分治可以讲的知识点很少,就和数学合并在一起讲啦!

二分和分治

二分

二分查找

定义

二分查找又称折半查找,它是一种效率较高的查找方法。

二分查找要求:线性表是有序表,即表中结点按关键字有序,并且要用向量作为表的存储结构。不妨设有序表是递增有序的。

基本操作

设R[low..high]是当前的查找区间

首先确定该区间的中点位置:

$$
mid = \left \lfloor \frac{low+high}{2} \right \rfloor
$$

将给定的关键字key与中间位置的元素进行比较。如果相等,则查找成功,如果不相等,则查找的元素一定在表的前半部分或者后半部分。继续缩小范围到前半部分或者后半部分再进行同样的查找,直到找到为止,或者查完之后仍然没有找到元素。

二分查找在查找失败时所需比较的关键字个数不超过判定树的深度,在最坏情况下查找成功的比较次数也不超过判定树的深度。即为 $\left \lceil \lg(n+1) \right \rceil$

二分查找的最坏性能和平均性能相当接近

二分答案

定义

二分答案与二分查找类似,即对有着单调性的答案进行二分,大多数情况下用于求解满足某种条件下的最大(小)值。

二分答案与二分查找类似,即对有着单调性的答案进行二分,大多数情况下用于求解满足某种条件下的最大(小)值。

答案单调性

《二分和分治&数学基础(二) —— 跟WilliamYan一起学算法》
答案的单调性大多数情况下可以转化为一个函数,其单调性证明多种多样,如下:

  1. 移动石头的个数越多,答案越大(NOIP2015跳石头)。
  2. 前i天的条件一定比前 i + 1 天条件更容易(NOIP2012借教室)。
  3. 满足更少分配要求比满足更多的要求更容易(NOIP2010关押罪犯)。
  4. 满足更大最大值比满足更小最大值的要求更容易(NOIP2015运输计划)。
  5. 时间越长,越容易满足条件(NOIP2012疫情控制)。
可以解决的问题
  1. 求最大的最小值(NOIP2015跳石头)。
  2. 求最小的最大值(NOIP2010关押罪犯)。
  3. 求满足条件下的最小(大)值。
  4. 求最靠近一个值的值。
  5. 求最小的能满足条件的代价。
代码

为了保证解在二分搜索的区间里,故不同的问题有着不同(但相似)的写法,读者可以画一个区间模拟一下~

求最小值
int binary()
{
    int l = 0, r = ll, mid;
    while(l < r)
      {
        mid = (l + r) >> 1;
        if(check(mid)) r = mid;  //大多数题只要改改check()即可
        else l = mid + 1;
      }
    return l;
}
求最大值
int binary()
{
    int l = 0, r = ll, mid;
    while(l < r)
      {
        mid = (l + r + 1) >> 1;
        if(check(mid)) r = mid - 1;
        else l = mid;
      }
    return l;
}
面对整数时的万能二分
int binary(int n)
{
    int l = 1, r = maxn, ans = 0;
    while(l <= r)
      {
        int mid = (l + r) >> 1;
        if(c[mid] > a[n]) ans = mid, l = mid + 1;  //判断条件与ans记录位置因题而异
        else r = mid - 1;
      }
    return ans;
}

例题:

跳石头(NOIP2015 Day2 T1)

算法分析:
本题具有二分答案的特征:如果给出一个距离s,验证行不行却比较容易:从左到右逐个检查,如果当前石头与前一个距离小于s,则将这块石头搬走即可,然后统计搬走石头的数量num,如果num<M则可行。注意最后一块石头到岸上的距离也要检查! 因此本题可以用二分答案的方法求解。

  1. 答案是否满足单调性:满足
  2. 二分区间:[1,L+1)
  3. 验证答案正确的方法:枚举每块石头,将间距小于s的石头搬走,统计搬走石头的数量,如果小于M则答案s可行。

分治

引例

分硬币问题

【问题描述】

​ 有n个硬币,其中有一个是伪币,重量和其他硬币轻,你有一个天平,你最少秤几次如何找到这个伪币呢?

在做出回答之前,先好好想想,所谓“最少称几次”,并没有限制每次称的次数,

带着这个问题,我们来学习分治的思想。

定义

​ 分治法是将一个难以直接解决的大问题,分割成一些规模较小的相同问题,在当前这一层划分中先处理一些内容,然后通过进一步这些规模小的相同问题合并信息可以获得答案。

分治难点在于对于时间复杂度的把控。大部分时候需要具体问题具体分析(多画分层图),但也有的时候,我们可以借助主定理:

《二分和分治&数学基础(二) —— 跟WilliamYan一起学算法》

关于二分和分治的题目,大家可以多去网上做一些。这是OI初赛常考的内容。

数学

集合

定义

集合(简称集)是数学中一个基本概念。

最简单的说法,即是在最原始的集合论——朴素集合论中的定义,集合就是"一堆东西"。集合里的"东西",叫作元素。若 $x$ 是集合 $A$ 的元素,则记作 $x\in A$ 。集合是把人们的直观的或思维中的某些确定的能够区分的对象汇合在一起,使之成为一个整体(或称为单体),这一整体就是集合。

组成集合的对象称为这一集合的元素(或简称为元)。

现代数学还用"公理"来规定集合。最基本公理例如:

外延公理:对于任意的集合 $S1$ 和 $S2$ ,$S1=S2$ 当且仅当对于任意的对象 $a$,都有若 $ a\in S1 $,则 $a\in S2$;若$a\in S2$,则$a\in S1$。

无序对集合存在公理:对于任意的对象 $a$ 与 $b$ ,都存在一个集合 $S$ ,使得 $S$ 恰有两个元素,一个是对象 $a$ ,一个是对象 $b$ 。由外延公理可得,由它们组成的无序对集合是唯一的,记做 ${a,b}$。 由于 $a,b$ 是任意两个对象,它们可以相等,也可以不相等。空集合存在公理:存在一个集合,它没有任何元素。

性质

确定性:每一个对象都能确定是不是某一集合的元素,没有确定性就不能成为集合,例如"个子高的同学""很小的数"都不能构成集合,"身高高于175cm的同学""小于7的数"就可以构成集合。这个性质主要用于判断一个集合是否能形成集合。

互异性:集合中任意两个元素都是不同的对象。如写成 ${1,1,2}$,等同于 ${1,2}$。互异性使集合中的元素是没有重复,两个相同的对象在同一个集合中时,只能算作这个集合的一个元素。

无序性:${a,b,c}{c,b,a}$是同一个集合。

纯粹性:所谓集合的纯粹性,用个例子来表示。集合$A={x|x<2}$,集合A 中所有的元素都要符合 $x<2$,这就是集合纯粹性。

完备性:仍用上面的例子,所有符合 $x<2$ 的数都在集合$A$中,这就是集合完备性。完备性与纯粹性是遥相呼应的。

其他性质:若 $A\subseteq B$,则 $A\cap B=A$ ,$A \cup B=B$

这些都是高中数学内容……

分类计数

加法原理

做一件事,完成它可以有 $n$ 类办法,在第一类办法中有 $m_1$ 种不同的方法,在第二类办法中有 $m_2$ 种不同的方法,……,在第 $n$ 类办法中有 $m_n$ 种不同的方法,那么完成这件事共有 $N=m_1+m_2+m_3+…+m_n$ 种不同方法。每一种方法都能够直接达成目标。

乘法原理

做一件事,完成它需要分成 $n$ 个步骤,做第一步有 $m_1$ 种不同的方法,做第二步有 $m_2$ 种不同的方法,……,做第 $n$ 步有 $m_n$ 种不同的方法,那么完成这件事共有 $N=m_1\times m_2\times m_3\times …\times m_n$ 种不同的方法。

区分两个原理

要做一件事,完成它若是有n类办法,是分类问题,第一类中的方法都是独立的,因此使用加法原理;做一件事,需要分n个步骤,步与步之间是连续的,只有将分成的若干个互相联系的步骤,依次相继完成,这件事才算完成,因此用乘法原理。

完成一件事的分“类”和“步”是有本质区别的,因此也将两个原理区分开来。

排列组合

排列

排列有两种定义,但计算方法只有一种,凡是符合这两种定义的都用这种方法计算。

  定义的前提条件是$m\leq n$,$m$与$n$均为自然数。

① 从$n$个不同元素中,任取$m$个元素按照一定的顺序排成一列,叫做从$n$个不同元素中取出$m$个元素的一个排列。

② 从$n$个不同元素中,取出$m$个元素的所有排列的个数,叫做从$n$个不同元素中取出$m$个元素的排列数。

③ 用具体的例子来理解上面的定义:4种颜色按不同颜色,进行排列,有多少种排列方法,如果是6种颜色呢。从6种颜色中取出4种进行排列呢。

  解:
$$
\begin{equation}
\begin{aligned}
A^4_4 &=4!\\
&= 4\times(4-1)\times (4-2)\times(4-3)\\
&=4\times 3\times 2\times 1\\
&=24\\
A_6^6 &= 6!\\
&=6\times 5\times 4\times 3\times 2\times 1\\
A^4_6 &= \frac{6!}{(6-4)!}\\
&=\frac{6\times 5\times 4\times 3\times 2\times 1}{2\times 1}\\
&=360
\end{aligned}
\end{equation}
$$

计算公式

排列用符号$A_n^m$表示,$m \leq n$。

计算公式是:$A_n^m=n(n-1)(n-2)……(n-m+1)=\frac {n!}{(n-m)!}$

此外规定$0!=1$,$n!$表示$n(n-1)(n-2)…1$

例如:$6!=6\times 5\times 4\times 3\times 2\times 1=720,4!=4\times 3\times 2\times 1=24$。

组合

组合的定义有两种。定义的前提条件是$m\leq n$。

① 从$n$个不同元素中,任取$m$个元素并成一组,叫做从$n$个不同元素中取出$m$个元素的一个组合。

② 从$n$个不同元素中,取出$m$个元素的所有组合的个数,叫做从$n$个不同元素中取出$m$个元素的组合数。

③ 用例子来理解定义:从4种颜色中,取出2种颜色,能形成多少种组合。

解:
$$
\begin{aligned}
C^2_4&=C_4^{4-2}\\
\\
&=\frac{A_4^2}{2!}\\
\\
&=\frac{\frac{4!}{2!}}{(4-2)!}\\
\\
&=\frac{\frac{4\times (4-1)\times(4-2)\times(4-3)}{2\times(2-1)}}{2\times (2-1)}
\\
&=\frac{(4\times 3\times 2\times 1)\div 2}{2}\\
\\
&=6
\end{aligned}
$$

计算公式

组合用符号 $C_n^m$ 表示,$m\leq n$。

公式是:$C_n^m=\frac{A_n^m}{m!}$ 或 $C_n^m=C_n^{(n-m)}$。

其它排列与组合公式

  • 其它排列与组合有三种。

    ① 从n个元素中取出m个元素的循环排列数=A(n,m)/m!=n!/m!(n-m)!。

    ② n个元素被分成K类,每类的个数分别是n1,n2,…,nk这n个元素的全排列数为n!/(n1!xn2!x…xnk!)。

    ③ k类元素,每类的个数无限,从中取出m个元素的组合数为C(m+k-1,m)。

    《二分和分治&数学基础(二) —— 跟WilliamYan一起学算法》

符号说明

  • C-代表-Combination–组合数

    A-代表-Arrangement–排列数(在旧教材为P-permutation–排列)

    N-代表-元素的总个数

    M-代表-参与选择的元素个数

    !-代表-阶乘

基本公式整理

  • 只要记住下面公式,就会计算排列组合:(在列式中n为下标,m为上标)

    排列

    A(n,m)=n(n-1)(n-2)……(n-m+1)=n!/(n-m)!

    组合

    C(n,m)=A(n,m)/A(m,m)=A(n,m)/m!

    C(n,m)=C(n,n-m)=n!/m!(n,m)!

=[排列组合 参考]: https://blog.csdn.net/qq_22642239/article/details/86594390 "重温排列组合"

其他公式:

$\sum_{i=0}^{n}C_n^i=2^n$

$C_0^n-C_1^n+C_2^n-……+(-1)^nC_n^n=0$

圆周排列

n个不同元素中取r个沿一圆周排列

$P_n^r = P_n^r / r$

$P_n^n = (n-1)!$

取重复元素组合问题

从n种不同的元素中取r个元素的组合,允许出现重复元素:

例题:r个相同的小球放到n个不同的盒子里,所有不同的放置方法?

$C^{\text{ } r}{\text{ }n+r-1} = C{\text{ }n+r-1}^{\text{ }n-1}$

错位排列

引入例题

在书架上放有编号为1,2,…….,n的n本书。现在将n本书全部取下再放回去,要求每本书都不能放在原来的位置上。

例如n=3时,原来的位置为1,2,3

放回去就只能是3,1,2或2,3,1。

求n=5时满足条件的方法?

定义

对于一个1…n的任意排列,要满足第i个位置上的数字不对应i。

例如,n=3时,只有2 3 1与3 1 2时满足要求的。

现在我们需要求出,能否对于任意数n给出错位排列(即错排)的个数?

递推关系:我们设一个整数k,且n=>k>1,代表的是当前枚举到的位置。

分两类:

注:以下的“1”仅是一个推理的辅助工具,不影响推理过程的准确性。

  1. 将k这个数字与1交换,其他的 $n-2$ 个数字错排,得到$D_{n-2}$

  2. 将k这个数字放在除它本身位置和1的位置的其他地方。

这一点有一点难度,我仔细说说。

我们先把1固定,让剩下的n-1个数字错排,方案数D(n-1)。

之后我们将错排后的许多种情况的k与1交换。

因为第二种情况下错排后k不会在k本来的位置,共有D(n-1)种情况。

所以在错排后1和k交换后1,1不会在k本来的位置,不与第一类情况重合。

所以第二种情况方案数D(n-1)。

因为k是大于1小于等于n且为整数(因为我们不可能在1的位置上放置1),所以我们要乘上n-1。

那么答案就是 $Dn=(n-1)*(D{n-1}+D_{n-2})$ ,再设一下边界,$D_1=0 , D_2=1$ 。

递推代码

long long cp[maxn];
inline void get_cp()
{
    cp[0]=1ll;
    for(int i=2;i<=n;i++)
        cp[i]=(i-1)*(cp[i-2]+cp[i-1])%mod;
}

梅森数

梅森数(Mersenne number)又称麦森数,是指形如2^p-1的正整数,其中指数p是素数,常记为Mp 。若其是素数,则称为梅森素数。

费马小定理

$a^p\equiv a \pmod{p}$

费马小定理是欧拉定理的一个特殊情况:假如n和a的最大公约数是1的话,那么

$a^{\varphi (n)} \equiv 1 \pmod{n}$

在这里$\varphi (n)$是欧拉商数。欧拉商数的值是所有小于n的自然数中与n没有公约数的数的量。假如n是一个质数,则φ(n) = n-1,即费马小定理。

逆元

定义

首先说明逆元的概念,类似于倒数的性质。

方程 $ax\equiv 1\pmod{p}$ 的解称为 $a$ 关于模 $p$ 的逆,当 $gcd(a,p)=1$(即 $a$ , $p$ 互质)时,方程有唯一解,否则无解。

对于一些题目会要求把结果MOD一个数,通常是一个较大的质数,对于加减乘法通过同余定理可以直接拆开计算,

但对于 $(a\div b)\bmod{p}$ 这个式子,是不可以写成 $(\frac{a\bmod{p}}{b\bmod{p}})\bmod p$ 的,但是可以写为 $(a\times b^{-1})$ ,其中 $b^{-1}$ 表示 $b$ 的逆元。

逆元和我们平时所说的倒数是有一定的区别的,我们平时所说的倒数是指 $a\times \frac{1}{a} = 1$,那么逆元和倒数之间的区别就是:假设x是a的逆元,那么 $a \times x \equiv 1 \pmod{p}$ ,也就是只多了一个取余的操作,这个取余的操作,就会保证 $a$ 的逆元不一定只是 $a$ 的倒数。

我们用 $inv(b)$ 来表示 $b$ 的逆元,那么他一定满足:$b\times inv(b) \equiv 1 \pmod{p}$ ==> $b = \frac{1}{inv(b)} $,那么我们代入上面的除法的式子:$(a\div b)\bmod{p} = (a \times inv(b)) \bmod{p} = (a\bmod{p} \times inv(b)\bmod{p})\bmod{p} $

这样我们就可以根据逆元来将除法取余的式子转换为乘法取余的式子

求法

我们这里先只介绍一种计算逆元的方式,利用费马小定理计算逆元

费马小定理:如果p是质数(素数),并且 $gcd(a,p) == 1$, 那么就会满足 $a^{p-1}\equiv 1 \pmod{p}$ ,当然了,既然 $p$ 已经是素数,那么如果 $a < p$ 那么就一定会满足这个式子,既然这样我们要得到 $a^{-1}$ 我们就可以利用上面的式子来计算 $a^{p-2} = inv(a) \pmod {p}$

这样我们就得到了我们需要的逆元。

实现:

long long quick_pow(long long a,long long b)
{
    long long ans = 1;
    while(b)
    {
        if(b & 1) ans *= a;
        a *= a;
        b >>= 1;
    }
    return ans;
}
quick_pow(a,p-2);

下面以HDU5685为例(文中 % 为取模运算符)

题目给出的hash计算法就是连续区间元素的乘积对9973取模,我们自然而然想到前缀积的方法,但是数很大,前缀积显然只能存下%9973后得值,

但有:(A/B)%M=(A%M*(B^-1%M))%M,A%M显然就是pre[A],B的逆对M取余就是qpow(B,M-2,M),快速幂模之即可。

#include<bits/stdc++.h>
using namespace std;
#define LL int
#define MOD 9973
LL inv[10000];
LL pre[100005];
char s[100005];
LL qpow(LL a,LL b,LL M){
LL r=1;
while(b){
    if(b&1) r=r*a%M;
    b>>=1;
    a=a*a%M;
    }
    return r;
}
int main()
{
    int N,i,j,k;
    inv[1] = 1;
    for(i=2;i<=9972;++i) inv[i]=qpow(i,MOD-2,MOD);
    while(scanf("%d",&N)==1){pre[0]=1;
        scanf("%s",s+1);
        int n=strlen(s+1);
        for(i=1;i<=n;++i){
            pre[i]=pre[i-1]*(s[i]-28)%MOD;
        }
        while(N--){int a,b;
            scanf("%d%d",&a,&b);
            printf("%d\n",pre[b]*inv[pre[a-1]]%MOD);
        }
    }
    return 0;
}

还有一种线性递推的方法:

inv[1] = 1;
for(i=2;i<MOD;++i) inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;  (isprime(MOD))

对于这个式子的证明:

M=k*i+r≡0 (mod M)

式子两边同乘上 i-1*r-1,如果M不是质数得话r就可能为零

​ k*r-1+i-1≡0 (mod M)

​ i-1≡M-floor(M/i)*(M mod i)-1 (mod M)

易证 <==> i-1=(M-M/i)*inv[M%i]%M;

还有就是拓展欧几里得算法,对于一些很大的数,用递推法非常耗时,但又不适用于快速幂的时候(可能会爆long long 无法得出正确结果),

考虑使用这个算法。

我们对这个算法进行推演一下,exgcd求解的是一组 ax+by=gcd(a,b) 的一组(x,y)的解,

我们设

​ ax1+by1=gcd(a,b)———————–1

​ bx2+(a%b)*y2=gcd(b,a%b)————2

根据朴素的欧几里得算法可得 1,2式的右端是相等的,同理左端也相等,

​ ax1+by1=bx2+(a%b)*y2

==> ax1+by1=bx2+(a-a/bb)y2

==>ax1+by1=ay2+b(x2-a/b*y2)

显然我们能得出 x1=y2; y1=x2-a/b*y2;

也就是说我们根据x2,y2便可推导出x1,y1的值,只要将a,b换成b,a%b即可,和gcd算法类似这是一个递归的过程,出口当b==0时,此时 x=1,y=0,gcd(a,b)=d=a;

对于ax+by=gcd(a,b)这个式子,当gcd(a,b)=1的时候,ax+by=1,根据逆元的定义可知x的解就是a关于模b的逆元,y的解就是b关于模a的逆元,当gcd(a,b)=d=1时成立。

(ax+by=1 –> ax(mod b)=(1-by) (mod p)=1 (mod p) )

这是gcd关于递推法的比较答案显然一致

#include<iostream>
using namespace std;
#define LL long long
#define mod 997
void gcd(LL a,LL b,LL &d,LL &x,LL &y)
{
    if(!b) {d=a;x=1;y=0;}
    else {gcd(b,a%b,d,y,x);y-=x*(a/b);}
}
LL finv(LL a,LL n)
{
  LL d,x,y;
  gcd(a,n,d,x,y);
  return d==1?(x+n)%n:-1;
}
int main()
{
    int inv[100]={1,1};
    for(int i=2;i<=99;++i){
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        cout<<inv[i]<<" "<<finv(i,mod)<<endl;
    }
    return 0;
}

对于逆元运算还有一些常见的式子,如:

${a^{-1}}^{-1}=a$
$(a\times b)^{-1}=b^{-1}\times a^{-1}$

对他们的证明:

设单位元为e.
x的逆元按定义是满足 $x\times y = y\times x = e$ 的元素y.
逆元是唯一的:设 $x\times y = y\times x = e,x\times z = z\times x = e $ ,有 $y = y\times e = y\times (x\times z) = (y\times x)\times z = e\times z = z$ .

  1. $a^{-1}$ 是 $a$ 的逆元,即有$a\times a^{-1} = a^{-1}\times a = e$ ,也即 $a^{-1}\times a = a\times a^{-1} = e$ .
    于是 $a$ 也是$a^{-1}$ 的逆元,可写为${a^{-1}}^{-1} = a$.
  2. $(a\times b)\times (b^{-1}\times a^{-1}) = a\times (b\times (b^{-1})\times a^{-1} = a\times e\times a^{-1} = a\times a^{-1} = e$
    $ (b^{-1}\times a^{-1})\times (a\times b) = b^{-1}\times (a^{-1}\times a)\times b = b^{-1}\times e\times b = b^{-1}\times b = e$ .
    于是$b^{-1}\times a^{-1}$ 是 $a\times b$ 的逆元,即有$b^{-1}\times a^{-1} = (a\times b)^{-1}$ .

=[逆元 参考01]: https://blog.csdn.net/li1615882553/article/details/80001473 "逆元"
=[逆元 参考02]: https://www.cnblogs.com/zzqc/p/7192436.html "数论学习_逆元意义及求法"
=原文中有个别语病。此处未作改正。

看到了一个 $\theta(n)$ 的做法发现太神了,虽然想起来是挺简单的

这个做法实际上是这样的,首先 $1−1\equiv1\pmod{p}$

然后我们设 $p = k\cdot i + r,~r < i,~1 < i < p$

再将这个式子放到 $\mod p$ 意义下就会得到
$$
k\cdot i + r \equiv 0 \pmod p
$$

两边同时乘上 $i^{-1}\cdot r^{-1}$ 就会得到
$$
\begin{eqnarray}
k\cdot r^{-1} + i^{-1} \&\equiv\& 0 \&\pmod p\\
i^{-1} \&\equiv\& -k\cdot r^{-1} \&\pmod p\\
i^{-1} \&\equiv\& -\left\lfloor\frac{p}{i}\right\rfloor\cdot \left(p\bmod i\right)^{-1} \&\pmod p\ \end{eqnarray
}
$$

于是就可以从前面推出当前的逆元了,代码也就一行

A[i] = -(p / i) * A[p % i];

=[来源]: http://blog.miskcoo.com/2014/09/linear-find-all-invert "[数论]线性求所有逆元的方法 作者:Miskcoo"

写在最后

因为快开学了,所以以后更新频率很有可能会慢下来——特别是原创部分。当然,我们还是会坚持尽量不咕咕咕的!
© 2019 WilliamYan

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据