noip入门自学（NOIP训练营集训笔记）

本文作者潘恺璠参加过清北学堂NOIP2017训练营提高组精英班，笔记非常详细。特分享给大家！基本数论相关笔记较多，为方便大家阅读，我们预计会分为三到四篇文章介绍给大家。

点击一下标题可查看其他相关笔记！

NOIP训练营集训笔记—基本数论（一）

NOIP2019年冬令营正在报名中，寒假和元旦都会开课，欢迎大家咨询报名！欢迎咨询报名NOIP2019冬令营！<-点击查看

基本数论（二）

15.欧拉定理：

费马小定理的推广：a^φ(m)≡1(mod m)。

补充一些同余的性质：

①反身性：a≡a(mod m)

②对称性：若a≡b(mod m)，则b≡a(mod m)

③传递性：若a≡b(mod m)，b≡c(mod m)，则a≡c(mod m)

④同余式相加：若a≡b(mod m)，c≡d(mod m)，则a±c≡b±d(mod m)

⑤同余式相乘：若a≡b(mod m)，c≡d(mod m)，则ac≡bd(mod m)

经典例题：给定数a、b、p，求a^x≡b(mod p)的最小正整数解x。

BSGS算法——“北上广深算法”或“拔山盖世算法”：

令x=im-j,m=⌈sqrt(p)⌉,则a^im-j≡b(mod p)，

移项，有：(a^m)ⁱ≡ba^j(mod p)

（也就是[(x y)!/(x!×y!)]），才能表示从两种情况中选择往x、y之一走的概率。

所以最终的概率为（对所有情况进行求和）：

这个式子很不好求啊！！肆意展示一下数学功底的时候到了！

我们改变枚举量进行化简！过程如下：

其中：

说明：在以上的推理过程中，打"*"的这一步和红框的推理过程：

①打红框这一步推理：

根据二项式定理，有（字丑不要介意；′⌒`）：

类比一下，有a=q,b=(1-q)，所以原式可以化简为(q 1-q)ⁱ=1ⁱ=1（太™聪明了啊！！）

②打"*"这一步推理：

直接是等比数列求和即可！

4.Problem 2.333333：

小葱想要过河，过河有两条路：

一条路有100个石头，每个石头有1/100的概率会挂掉。

另一条路有1000个石头，每个石头有1/1000的概率会挂掉。

小葱应该走哪条路呢？（请勿使用计算器）

5.Problem 3（这道题太丑被丢掉了）：

小葱在平面上画了很多条平行等间距为l的直线，小葱将长度为1的针投到这个平面上，求针和直线相交的概率？

典型的蒲丰投针问题：

分情况讨论：

①当l≤1：

②当l>1：

6.Problem 4：

小泽在数轴上的0点处，他每次有r的概率向右走，有1-r的概率向左走，求小泽走到-1处的概率为？

解法：如果直接列式求和计算：大量组合数求和！卡特兰数！级数！（mmp看得我想死）

设到达x-1的概率为p，则p=(1-r)×1 r×p×p 第一步向左走到-1的概率 第一步向右走回到-1的概率（往左走两次到-1）

根据上式，变形得：rp²-p 1-r=0，解方程可得到：p=(1±|2r-1|)/2r，因为有绝对值，所以分类讨论2r和1的关系：

经过紧张又激烈的讨论，我们得出一个分段函数（r都可以取）：

7.Problem 5：

小胡有一棵一个点的树，小胡会给这个点浇水，于是这个点会有的概率长出两个儿子节点。

每次长出新的节点之后，小胡又会给新的节点浇水，它们也都有的概率长出两个新的儿子节点。

小胡不希望自己被累死，所以小胡希望知道这棵树的大小是有限的的概率。

解法：这道题和上一题是一毛一样的！

8.经典题1：

给出n行m列矩阵，k次操作，每次操作选取一个子矩阵，子矩阵内的所有矩阵标记，做了k次操作内，被重复标记的标记为已标记。

求：k次操作后，对于左上角坐标为(x,y)的矩形，至少被1个子矩阵包含的概率为多少？

例如：下面一个2×2的矩阵：

当k=1时，有9种标记方法：

而我们总共能够标记1×4 2×4 4×1个矩阵，所以得到的概率为1/9×(1×4 2×4 4×1)=16/9。

推理过程：

假设k=1时，我们来观察一个3×4的矩阵：

要使得A包含这个红色的矩阵B，那么这个矩阵A的左上点和右下点应该在蓝色的区域，这样才能保证完全覆盖红色矩阵。

假设这个矩阵的左上的点为(x,y)，右下的点为(n-x 1,m-y 1)，在这个图形里面总共有：(1 2 3 … n)=[n×(n 1)×m×(m 1)]/(2×2)个矩阵，并且满足蓝色文字的条件后，矩阵一共有：x×y×(n-x 1)×(m-y 1)个，所以概率为：x×y×(n-x 1)×(m-y 1)/{[n×(n 1)×m×(m 1)]/(2×2)}。

9.经典题2：

有n个点，坐标为(x₁,y₁)，(x₂,y₂)，(x₃,y₃)，…，(x_n,y_n)，求一个圆，包含这所有的点，并且保证半径最小。

暴力解法：枚举三个点，算出圆，把剩下的点全部丢进去判断在不在里面，算法复杂度：O(n⁴)

优化暴力解法O(n³)：

for(int a=1;a<=n;a )//往已知圆内一个一个地丢点

{

if(!in(p[a])) circle=cir(p[a]);//a不在圆内

circle=cir(p[a]);//构造以a位圆心的圆

for(int b=1;b<=a;b )

{

if(!in(p[b])) circle=cir(p[a],p[b]);//构造以a、b两点为直径的圆

for(int c=1;c<=b;c )

{

if(!in(c)) circle=cir(p[a],p[b],p[c]);//构造a、b、c三点共圆的圆

}

}

}

最优雅地优化O(n)：利用C 中的一个函数叫：random_shuffle（随机打乱n个点的顺序），可以将时间复杂度优化到O(n)，怎么样？很神奇很诡异吧？？！

思想就是：随机选三个点形成一个圆，于是接下来的那些的点进入下面两个for循环的概率实际上很小！

欢迎咨询报名NOIP2019冬令营课程！<-点击查看详情

咨询方式：

司老师 18610112920 赵老师 18610112915 高老师18611056259 老师 18611083835 张老师 18610150289

定期推送帐号信息学新闻，竞赛自主招生，信息学专业知识，信息学疑难解答，信息学训练营信息等诸多优质内容的wx公众平台noipnoi

,