NOIP 2018 集训 Day 5

这是最后一篇即时笔记了呢

数学

数论

数论各种神器算法

线性递推逆元：$i^{-1}=(p-\lfloor p\div i\rfloor)\times (p\%i)^{-1}\% p$。

以及阶乘和阶乘的逆元的递推：$n!\equiv n\times (n-1)! \pmod{p},(n!)^{-1}\equiv n^{-1} \times ((n-1)!)^{-1}$。

可以用这个方法在$\text{O}(n)$预处理后，$\text{O}(1)$计算组合数。

线性筛

这个线性筛不仅可以筛质数，还可以计算积性函数。$\varphi,\mu$等函数都可以用这种方法计算。详见贾志鹏 线性筛。

随机数生成器

可以用矩阵，也可以用等比数列求和。

这里介绍一些等比数列求和的方法。

现在我们要求$s=\sum_{i=0}^{n}a^i=1+a+a^2+\cdots+a^n \pmod{p}$。

如果$p$是质数，我们就可以利用等比数列的求和公式$s=\frac{a^{n+1}-1}{a-1}\equiv (a^{n+1}-1)\times (a-1)^{-1} \pmod{p}$。时间复杂度$\text{O}(\log n)$。

如果$p$不是质数，则答案可以如下计算：$(a^{n+1}-1)\% ((a-1)p)\div (a-1)$。

上述方法可概括如下：若$c=\frac{a}{b}$是整数，那么$c\% p=(a\%(bp))\div b$。（注意$a$不能边算边模，$a$一定要保持原样，即必须保证参与计算的$b\mid a$。如果要涉及到更复杂的膜 蛤 模合数，请参见Virtual NOIP Day 2 总结。）

证明如下：设$c\equiv x \pmod{p},a\equiv t \pmod{bp}$。

由同余的性质得，$c-x=np,a-t=bmp$。

将$c$的定义带入得：$\frac{a}{b}-x=np$，知$a-bx=bnp$。得$a=bnp+bx$。

又知$a=bmp+t$，带入得$bnp+bx=bmp+t$，即$bx-t=bp(m-n)$，知$bx\equiv t \pmod{bp}$。

由$a-t=bmp$知$bc-t=bmp$，得$t=b(c-mp)$。令$k=c-mp$，则$t=bk$。

带入得$bx\equiv bk \pmod{bp}$，约去$b$得$x\equiv k\pmod{p}$。证毕。

当然还可以用分治。现在要求$s=\sum_{i=0}^{n}a^i=1+a+a^2+\cdots+a^n \pmod{p}$。

如果$n$是偶数，设$n=2k$，那么$s=1+a+\cdots+a^k+a^{k+1}+\cdots+a^{2k}=(1+a^{k})(1+\cdots+a^{k-1})+a^{2k}$

如果$n$是奇数，设$n=2k+1$，那么

$s=1+a+\cdots+a^k+a^{k+1}+\cdots+a^{2k+1}=(1+a^{k+1})(1+\cdots+a^k)$

取边界条件$k=0$，分治即可。

解方程

系数这么大，怎么办？写高精

写高精是不可能的，这辈子都不会写高精的！

我们考虑把方程弱化为同余方程，取一个大数~~（比如某个数）~~，最好是$\text{long long}$级别的，读入时直接把系数模$p$，然后枚举解即可。

Freda城堡的密码

取$\text{long long}$级别的Dark♂数，预处理出$F_1,F_2,\cdots,F_{100000}$模这个数的余数，枚举判断即可。

随机数生成的方法

最简单的方法当然是直接rand()（是否srand()都可以）。

下面介绍一种生成（几乎）不可预测的随机数的方法，对于$\text{OI}$赛制来说没有什么用，但是对于$\text{Codeforces}$这种需要防$\text{hack}$的赛制，就很有用了。

1
2
3
4

void *a=new char;
void *b=(void *)(NULL);
int x=a-b;
delete a;

上述代码会生成一个随机数$x$，请注意$x$一定是$8$的倍数。

小凯的疑惑 遗憾

考场上怎么办？数论打表找规律！千万不要像我一样蠢到手算，面前摆的可是一台高科技计算机呢，怎么能不写程序找规律呢？找找规律就发现是一次函数了w_w。

证明我有时间再补吧。

看一道推广题：半质数的线性组合

结论是$2pqr-pq-pr-qr$。

欧拉函数（$\varphi $函数）

$\varphi(x)=\sum_{i=1}^{x}[i \perp x]$，即$[1,x]$中与$x$互质的数的个数。

$\varphi(ab)=\varphi(a)\varphi(b) \ \text{ }(a\perp b)$

中国生育剩余定理

$\text{long long} \text{ O}(1)$ 快速乘

有时候我们要计算$a\times b\% p$，其中$a,b,p$都是$\text{long long}$级别的数字，那么我们怎么办呢？

有一个玄学类型，叫做$\text{long double}$，它作为浮点数类型，可以保存相当大的数，误差相对不是很大。

再回顾一下模的概念：$x\%p=a-\lfloor\frac{x}{p}\rfloor \times p$。

于是我们的思路就是，用$\text{long double}$暂时算出积的值并除以$p$，加上一点微小的$\text{EPS}$，转换为$\text{long long}$后乘以$p$，再用$\text{long long}$下积的值减去上面计算的结果，加上$p$后再模$p$即可。

上面说起来比较抽象，让我们看看代码。

1
2
3
4
5
6
7
8
9
10
11

ll mul(ll a,ll b,ll p){
	ll res;
	a%=p;
    b%=p;
    res=(ll)((long double)(a)*b/p+EPS);
    res=res*p;
    res=a*b-res;
    res+=p;
    res%=p;
    return res;
}

压行后的代码如下：

1
2
3
4

ll mul(ll a,ll b,ll p){
    a%=p,b%=p;
    return (a*b-(ll)((long double)(a)*b/p+EPS)*p+p)%p;
}

注意这个方法在数字较大的时候很可能不准确，如果要保险，请使用龟速乘（$\text{O}(\log n)$）。

1
2
3
4
5
6
7
8
9
10

ll mul(ll a,ll b,ll p){
    ll ans=0;
    while (b){
        if (b&1)
            ans=(ans+a)%p;
        a=(a<<1)%p;
        b>>=1;
    }
    return ans;
}

组合数学

$\text{Catalan}$数

可以用生成函数解（学长的方法），也可以用图形直接转化为组合数（米尔嘉的神奇方法）。

$C_{n}=\frac{(2n)!}{(n+1)!n!}$可以表示：

1. 有$n$个结点的不同形态的二叉树的个数
2. 含$n$对括号的合法括号序列的个数
3. 长度为$n$的入栈序列对应的合法出栈序列个数
4. 通过连接顶点而将$n+2$边的凸多边形分成三角形的方法个数

根据$\text{Catalan}$数公式的推导过程，可以用$C_{n}=\text{C}^{2n}_{n}-\text{C}^{2n}_{n+1}$进行无除法的递推。

合法括号序列

将问题分解为，按键$n$次输入一个长度为$m$的序列和长度为$m$的序列有多少个是合法括号序列。前者可以通过$\text{dp}$计算，而后者就是$\text{Catalan}$数，最后将这两个相乘再累加即得答案。

子集选取

注意到每个元素的选取是独立的。

考虑某一个元素的选取，将选取方案转化为三角形上的折线，因此答案为$2^{nk}$。

卢卡斯定理

应用：愚蠢的组合数

概率论

茶壶

最优策略一定是选当前剩下的最贵的壶。将壶的价格从小到大排序为$a_1,a_2,\cdots,a_{2n}$。那么第$i$个壶被选中的概率是$p_i=\frac{i-1}{2n-1}$，于是总期望$\text{E}=\sum_{i=1}^{2n}p_{i}a_{i}$。

$\text{NOIP }2018$初赛$\text{T8}$

结论：在$[0,1]$内找$n$个数，其中最大数的期望是$\frac{n}{n+1}$，最小数的期望是$\frac{1}{n+1}$。

期望

• 独立事件：若$\text{P}(AB)=\text{P}(A)\text{P}(B)$，则$A$和$B$是独立的。

• 期望的性质：线性性：$\text{Ex}(aX+bY)=a\text{Ex}(X)+b\text{Ex}(Y)$
  独立随机变量的期望：若$X,Y$独立，则$\text{Ex}(XY)=\text{Ex}(X)\text{Ex}(Y)$

• 条件概率。