从零开始的数学
zhendelan
·
2021-01-20 14:23:17
·
个人记录
0
数学题选做。 （慢慢补我那可怜的数学,持续更新）
1
P1290 欧几里德的游戏
显然，当\frac {x} y \geq 2 时，先手都是必胜的，因为先手可以任意到达后手或先手的(y,x\mod y) 。 否则走的方法是唯一的。
代码
2
P1247 取火柴游戏
显然是一个SG游戏。SG(S)=mex(SG(T_1),SG(T_2)...) 。可以归纳出SG(S)=S 。0 则先手必败，否则必胜。
必胜态要决定第一步怎么走，显然就是让异或为0 。一个一个枚举即可。
代码
3
威佐夫博弈
这个情况颇为复杂。
前几个奇异局势为：(0,0),(1,2),(3,5),(4,7),(6,10).... 。
找找规律是这样的：设点对为(a_i,b_i) ,从0 开始。
- 显然每个非负整数都会且仅会在一个奇异局势中。
- 显然任意操作都会将奇异局势变得不奇异。
- 每个不奇异局势都可以变成奇异局势。
第三个性质的讨论比较复杂，可以上网搜。（其实感觉也比较显然）。
那么只需要判断现在是否是奇异局势就可以了。
有公式$a_i=[k\frac{\sqrt 5 + 1} 2],b_i=a_i+i$。
你不得不说我是个傻逼,我还用了二分。
[代码](https://www.luogu.com.cn/paste/p88ewg1b)
## 4
高精度除法，弄了很久发现不可做，爬了。
## 5
[P5577 [CmdOI2019]算力训练](https://www.luogu.com.cn/problemnew/show/P5577)
好难。下一个。
## 6
[P5343 【XR-1】分块](https://www.luogu.com.cn/problem/P5343)
可能我就只配做这种题吧。。。。
显然矩阵快速幂。
[代码](https://www.luogu.com.cn/paste/awxdysln)
## 7
[P5337 [TJOI2019]甲苯先生的字符串](https://www.luogu.com.cn/problemnew/show/P5337)
同上。
[代码](https://www.luogu.com.cn/paste/o3m3iw4m)
## 8
[P4967 黑暗打击](https://www.luogu.com.cn/problem/P4967)
一道看似简单却并不简单的题目。
先找递推式：
这个我还真不会。我是找OIES的。
OIES告诉我是这样的：
$f(n)=6f(n-3)-10f(n-2)+4f(n-3)
我就先按着这个式子算 。
显然是矩阵快速幂。
但是模数太大了。需要乌龟乘。
而且n 太大了，需要用到费马小定理,a^{\phi (p)}=1 。。
这个在矩阵乘法中同样适用。（我觉得感性理解就可以了吧。）
代码
关于递推式：
设f(n) 为答案。
设g(n) 为n 的矩形转置后的结果。
所以f(n)=2f(n-1)+2g(n-1)+2^n - 2
g(n) = f(n-1)+2g(n-1)+2^{n-1}-1
这个同样可以构造矩阵，快速幂。。
9
P4781 【模板】拉格朗日插值
基本推导
其实就是给出平面上n+1 个点(x_i,y_i) 。求经过他的n 次多项式。
直接给结论就是：
设拉格朗日基本多项式为：
\zeta_i(x) =\prod_{j=0,i\neq j}^n \frac {x-x_j} {x_i-x_j}
f(x)=\sum_{i=0}^ny_i(\prod_{j=0,i\neq j}^n\frac {x-x_j} {x_i-x_j}) = \sum_{i=0}^n y_i \zeta_i(x)
这是一个巧妙的构造。
可以发现\forall x_i,j\neq i,\zeta_i(x)=1,\zeta_j(x)=0,f(x_i)=y_i 。
且恰好他是一个n 次多项式。
不难发现以上插值的过程是O(n^2) 的。
x连续时的插值
但在x 取值连续的时候，我们可以做到O(n) 。
那么\zeta_i(x)=\prod_{j=0,i\neq j}^n\frac {x-j}{i-j}
考虑如何计算\zeta_i(x) ,对于分子，我们预处理出前缀积和后缀积。
即pre_i=\prod_{j=0}^i{k-j},suf_i=\prod_{j=i}^n k-j 。
分母的话，不难发现其实就是i!(n-i)! ，但是有符号问题。当n-i 是奇数的时候，上面要取反。
所以
|f(x)|=\sum_{i=0}^n y_i \frac{pre_{i-1}*suf_{i+1}} {i!(n-i)!}
特别地,pre_{-1}=1,suf_{n+1}=1 。
重心拉格朗日插值
已知
f(x)=\sum_{i=0}^ny_i(\prod_{j=0,i\neq j}^n\frac {x-x_j} {x_i-x_j})
令 g = \prod_{i=0}^n x-x_i
f(x)=g\sum_{i=0}^n\frac {y_i} {(x-x_i)\prod_{j\neq i} (x_i-x_j)}
令t_i = \frac {y_i} {\prod_{j=0,j\neq i}^n (x_i-x_j) }
那么
f(x) = g\sum_{i=0}^n\frac{t_i}{x-x_i}
没看出来有什么用，可能动态加点删点有点用。
一些没啥用的应用
求f(n) = \sum_{i=1}^ni^k(n \leq 1e15,k\leq 1e6) 。
这个其实在NOIP2020微信步数中用到了，当然你可以在知乎看到很多关于这个问题的回答。
有人会告诉你f(n) 是k+1 次的多项式。（我也不知道谁会告诉你
将前k+2 个点带入后O(k) 插值即可。
模板题代码
10
P5158 【模板】多项式快速插值
还有前置知识，打扰了。
11
P3306 [SDOI2013] 随机数生成器
BSGS模板题
模型 1 :求解 a^x = b\mod p ,(a,p)=1
令t = \lceil p \rceil
令x=At+B,A,B\in[0,t]
那么a^{At-B} = b \mod p
有a^{At}=ba^B 。因为a,b 都是已知的，我们可以枚举B ，用哈希来记住所有右边的取值。然后在枚举A ，看看右边有没有。
可得到复杂度为O(\sqrt P) ，因为可以预处理出a^t 。一路乘过去，所以并没有快速幂的复杂度。
也可以用\text{map} ，多一个\log 。
模型 2 :求解 x^a = b\mod p , p\in prime
可以将模型2 转化成模型1 。
具体的，我们需要阶和原根 的知识。
篇幅问题，我们可以移步观看
方法1
令x^a = (g^c)^a
也就转化成了：(g^a)^c = b \mod p 。
因为a,b,g,p 已知，要求c ，已经可以转换成上面的模型1 了。
方法2
先解方程：g^t=b ，可以用模型1 。
那么g^{ac}=g^t ,取离散对数可得（好高级的名词）ac =t \mod \phi(p)
可以用扩展欧几里德求解。因为\gcd(\phi(p),a)=? 。
这里的有没有解情况也反映了方程的解的情况。
找出所有解
在知道x_0 = g^c \mod p 后，我们想要知道原方程的所有解。
因为g^{\phi(p)}=1 。
\forall t\in \mathbb{Z},x^a=g^{ac+t\phi(p)}=b
得到所有解为：
\forall t\in \mathbb{Z},a|t\phi(p),x=g^{c+\frac{t\phi (p)}a}
对于上面这个式子，显然有\frac{a}{\gcd(a,\phi(p))}|t 。因此我们设t = \frac {ai} {\gcd(a,\phi(p))} 。
所以\forall i \in \mathbb{Z},x=g^{c+\frac {i\phi(p)} {\gcd(a,\phi(p))}}
扩展
我们求解 a^x = b \mod p 。
其中a,p 不一定互质。
想办法让他们变得互质。
设d_1=\gcd(a,p) 。如果d_1 \not| b 。原方程无解。
得到：
\frac {a} {d_1} a^{x-1} = \frac b {d_1} \mod \frac p {d_1}
如果a 和\frac {p} {d_1} 不互质就继续除，设d_2=\gcd(a,\frac{p} {d_1}) 。如果d_2 \not| \frac {b} {d_1} ，方程无解。
否则继续。。
知道互质。
记D = \prod_{i=1}^k d_i
方程会变成：
\frac {a^k} D a^{x-k} = \frac b D \mod \frac{p} {D}
由于(a,\frac p D)=1 ,推出(\frac {a^k}D,\frac p D)=1 。这样\frac {a^k} D 就有逆元了。
求解x-k 即可。
注意，不能排除小于等于k 的情况，消因子前要O(k) 枚举一下。
上面的题的代码
12
P4139 上帝与集合的正确用法
首先要知道扩展欧拉定理：
对于\forall b\gt \phi(p) , a^b = a^{b \mod \phi(p) +\phi(p)} \mod p ，不要求(a,p)=1 。
这题可以先线性筛求出\phi(p) 。
然后递归找答案即可。
按照\phi 来下降，感觉跑的很快。
代码
13
P3200 [HNOI2009]有趣的数列
第一眼看上去还以为是多项式。。
手推一下可以发现是个括号序列合法个数，然后就变成卡特兰数了。
考虑怎么求：\frac {\binom {2n} {n}} {n+1} \mod p 。
其实就是不能直接求。
上式为：\frac {\prod _{i=n+2} ^{2n} i}{\prod_{i=1}^n i} 。
可以分解质因数，计算每个出现多少次就可以了。
我直接用的暴力筛加暴力。
不知道怎么算复杂度，感觉就是O(n \log n) 的，起码不会超过O(n \log n \log \log n) 。
14
P4718 【模板】Pollard-Rho算法
首先要知道Miller-Rabin素性测试。
可以根据费马小定理的出一个错误的思路：
因为当p\in prime 时，a^{p} = a \mod p 。
我们可以随机抽取几个基a 来判断。
但是很遗憾，费马小定理的逆定理并不正确。
即存在x\notin prime,\forall a,a^x = a \mod x 。
如561 。这种数我们把它成为卡迈克尔数，又称伪素数。
二次探测定理
如果p 是奇素数，x^2 = 1 \mod p 的解为x=1 或x=p-1 。
实现
根据卡迈克尔数的性质，其不可能是p^e （在a=p 时会错）。
所以可以将二次探测定理和费马小定理结合。
下面是检测n 的过程。还是随机底。
判断a^{n-1} = 1 。如果不是显然不是。
那么再判断a^{\frac {n-1} 2} =1 或n-1 。
如果是1 就继续下去。
实际时会反过来。
即先把n-1 中2 的因子全部去掉，令n-1=x2^k 。
将x 不断乘2 ，用二次探测定理判断即可。
Pollard-Rho
我们想分解一个大数。不妨猜他一个质因数是多少。但这样显然很难猜对。
可以类比猜班上那一天有人生日，这个猜中的概率显然也不高。但是如果我们猜有两个人生日相同，这个概率就会很高。
生日悖论
人话就是同一个班内有两人生日同一日的概率在n 不大的时候就非常趋近1 了。
即组合采样更容易取到某个数。
例如我们可以随机选择若干个数。
如果$(|x_i-x_j|,N)\gt 1$，那么$(|x_i-x_j|,N)$就是$N$的一个因子。
老祖宗告诉我们大约要选$N^{1/4}$个。但是这样要两两比较并不优秀。
我们考虑一下相邻取$\gcd$。
#### 生成一个随机数列
PR用函数$f(x)=x^2+c \mod (...)$来随机。
但是这个函数会有环。就像$\rho$一样。
#### Floyd判环
这个较为显然，可以上网查。
然后就可以得到一个比较基础的，基于$\text {floyd}$判环的算法：
[初代代码](https://www.luogu.com.cn/paste/4x7xm8ds)
#### 基于倍增的常数优化
因为$\gcd$自带$\log$，频繁的调用这个函数会导致时间复杂度变劣。
我们想让他少用一点。
$gcd(a,b)>1\to gcd(ac,b)>1 \to gcd(ac \mod b,b)>1
我们可以把所有测试样本乘起来做\gcd 做判断。
我们不妨考虑倍增思想，每次在路径\rho 上倍增地取一段[2^{k-1},2^k] 区间。我们在上面走时可以积累样本，当样本达到一定数量，我们才进行\gcd 。
但积累太多显然也是不好的，前辈告诉我们当样本长度超过127 就停止积累样本。至于为什么，我也不知道。
但是我不会告诉你，因为要乌龟乘，这个屁用没有。
简单的代码就放这：
qwq
抱歉，我错了。
发现如果用龟速乘，是不可能通过这道模板题的。。
那么我们用int128，听说有光速乘，不会。
然后不倍增会被卡常。
好了，然后就算了=-=。
代码
15
P4457 [BJOI2018]治疗之雨
我这个菜逼不知道在纠结什么东西。
我一直在考虑先减到0 以下，然后加不回来的情况。。根本就不存在。。。
设p[i] 为受到i 点伤害的概率。
p[i] = (\frac 1 {m+1})^i(\frac m {m+1})^{k-i}\binom k i
可以线性求出。
那么根据情况列方程即可。
注意：
$E_0$的项都忽略不计，因为$E_0=0$，且$E_0$的系数难以确定。
然后高斯消元就可以拿到$O(n^3)$的分。
可以发现系数矩阵上面第$i$行只有$[1,\min(i+1,n)]$这个区间有值。
发现每一行消完之后，当前都有剩下的一行只有两个元。可以$O(n^2)$消元。
[代码](https://www.luogu.com.cn/paste/suuc53ht)
### 16
[P4151 [WC2011]最大XOR和路径](https://www.luogu.com.cn/problem/P4151)
神仙题。
答案肯定是一条链加上若干个环。
丢到线性基里即可。
[代码](https://www.luogu.com.cn/paste/dqzvadxv)
### 17
[P3292 [SCOI2016]幸运数字](https://www.luogu.com.cn/problem/P3292)
树链线性基。
用树剖感觉会假（因为要暴力跑非整条重链的）。
不过感觉也可以区间线性基合并。详见我的[线性基学习笔记](https://www.luogu.com.cn/blog/gsh/xian-xing-ji)
也可以倍增。
区间线性基合并显然是3log的。
倍增建的时候也是3log的。但在查询时可以用ST表的思想做到2log(详见逛森林)。
~~在这题中优势很大~~
可惜的就是我没用也过了。=-=
[没用ST表的代码](https://www.luogu.com.cn/paste/fi664az4)
### 18
[P5303 [GXOI/GZOI2019]逼死强迫症](https://www.luogu.com.cn/problem/P5303)
经典整式递推不会推式子。
如果我会BM就好了
关注到如果没有限制的话就是一个斐波那契数列。
设答案为$f_i$。
如果没有两块碎石头，那就有:$f_{i-1}+f_{i-2}\to f_i$。
现在假如有，并且放在最右边。
那么显然另一块可以放在：$1 ...i-2$。
且中间方案数是唯一的。
设$g_i$为斐波那契数列左移一位，即$g_2=2$。
那么有$\sum_{i=1}^{i-3}g_i \to f_i$。
因为斐波那契数列的前缀和$h_i$就是$g_{i+2}-2$。
所以$f_i =f_{i-1}+f_{i-2}+2g_{i-1}-2$。
矩乘加速即可。复杂度$O(5^3T\log n)$，实际上可以通过预处理$B$加向量做到：$O(5^3\log n + 5^2T\log n)
代码
去OEIS观望了一下，应该没有比5 还小的矩阵了。
19
P5339 [TJOI2019]唱、跳、rap和篮球
感觉比较套路，但是我的目前水平还不会做的题。
显然让他不出现比较困难。所以要用容斥转化为出现。
当然可以直觉得，也可以用反演。
现在是求$f(0)=\sum_{i=0}^n(-1)^ig(i)$。
现在得问题就是求$g(x)$。
事实上$g(x)$是一个五元函数$f(n,a,b,c,d)$，用来计算$a,b,c,d$长度为$n$得排列数量。
除了$f$,还要考虑枚举的连续四个放在哪里。
这里我没想到如何枚举多个的时候这些位置放在哪里。
实际上就是把每$4$个缩成$1$个。这样所有的方案都对应着在$n-3i$的串里选$4$个，也就是$\binom {n-3i} 4$。
现在只需要知道$f$怎么求就可以了。
$f(n,a,b,c,d)=\sum_{i=0}^a\sum_{j=0}^b\sum_{k=0}^c\sum_{l=0}^d[i+j+k+l=n]\frac {n!} {a!b!c!d!}
这是一个四元卷积，暴力NTT即可，时间复杂度O(n^2 \log n) 。
代码
但是还有一些其他的做法。
如先让d 不用枚举，然后再用优化至O(n^4) 。
然后再用前缀和优化至O(n^3)
实际上也可以通过此题。
但还有比较特殊的性质就是每次将容斥的i 加一时，其实都只是每个多项式后面加了一个东西。
可以暴力维护两个多项式。
因为只用求一项，所以可以直接O(n) 查询 。
总时间复杂度O(n^2)
神仙EI还有O(n^\frac 3 2) 的做法。但是我一看就不会。
20
P4336 [SHOI2016]黑暗前的幻想乡
又是一道不会的计数题。
先介绍一下 Matrix-Tree 定理。
设一个无向图的度数矩阵和邻接矩阵分别为D,A 。
允许重边，邻接矩阵上记录的是有多少条边。
令K=D-A 。
矩阵树定理告诉我们Kirchoff矩阵满足一下性质：
行列式|K| 去掉任意一行一列 后相等。
行列式|K| 去掉任意一行一列 后即为生成树个数。
特别地，简单完全图的生成树个数为：n^{n-2} 。
至于证明，无非是归纳和冗杂的分类讨论。
。。傻逼了。怎么看完MT定理还不会啊。。。
现在只有两个限制：
令m=n-1 。
注意到集合并不等价。所以不能用二项式反演。
只能枚举集合强行做。
时间复杂度：O(2^m m^3 \log w) 。
实际上：通过辗转相除可以做到：O(2^m m^3) 。
详见学长lzh的题目：P7112 【模板】行列式求值
之前我应该还是第二个A这道题的，可是现在常数要求提高了，我都过不去了。0.0。
代码
21
P2791 幼儿园篮球题
学长lzh出的题。
并不是很难的样子。
求：
=\sum_{x=0}^{\min\{m,k\}}\binom mx\binom {n-m}{k-x}x^L
=\sum_{x=0}^{\min\{m,k\}}\binom mx\binom{n-m}{k-x}\sum_{i=0}^LS(L,i)i!\binom x i
=\sum_{i=0}^LS(L,i)i!\sum_{x=0}^{\min\{m,k\}}\binom mx\binom{n-m}{k-x}\binom x i
=\sum_{i=0}^LS(L,i)i!\binom m i\sum_{x=0}^{\min\{m,k\}}\binom{n-m}{k-x}\binom {m-i} {x-i}
=\sum_{i=0}^LS(L,i)i!\binom m i\binom {n-i}{k-i}
时间复杂度O(SL+N+M)
代码
又喜提最劣解 了
22
P6620 [省选联考 2020 A 卷] 组合数问题
ohno。大家都认为的去年省选签到题，我还是不会做。
我觉得这题比上面那道还有求和什么的难啊。
开始推式子。因为x 是个常数，所以我们并不用去斯特林反演x^k ，而是去反演多项式f(k) 。
经过普通的操作之后会这样：
\sum_{i=0}^m a_i \sum_{j=0}^i S(i,j)\sum_{k=j}^n x^k\frac {n!}{(n-k)!(k-j)!}
问题是后面的n 如何快速计算。
说实话，我觉得很难看出来后面的组合数。但是确实是可以看出来的。
也可以根据下降幂的结论看出来：
因为\binom nr = \frac n r\binom {n-1} {r-1}
递归下去可以得到：r^{\underline i}\binom nr=n^{\underline i}\binom {n-i}{r-i}
将上面的转成下降幂之后容易推。
但其实也可以这样：推的时候会知道我们的目标是使用二项式定理。注意到：(n-k)+(k-j)=n-j
我们构造一个组合数\binom {n-j} {k-j} ，就可以构造一个只关于n,j 的下降幂，与k 无关。
原式=
\sum_{i=0}^m a_i \sum_{j=0}^i S(i,j)\sum_{k=j}^n \frac {n!} {(n-j)!}x^k\binom {n-j} {k-j}
=\sum_{i=0}^m a_i \sum_{j=0}^i S(i,j)x^j\frac{n!}{(n-j)!}\sum_{k=j}^n x^{k-j}\binom {n-j} {k-j}
=\sum_{i=0}^m a_i \sum_{j=0}^i S(i,j)n^{\underline j}x^j(1+x)^{n-j}
然后就做完了。关键有两个：二项式定理与组合数转换
代码
23
P4720 【模板】扩展卢卡斯
先讲一讲普通卢卡斯：
\binom n m =\binom {n/p} {m/p} \binom {n \mod p}{m\mod p} \mod p,p\in prime
不会证，用就好了。p\notin prime ,要用CRT合并。将p 拆成p_1^{k_1}p_2^{k_2}...p_x^{k_x} 。
现在就是要求：\frac {n!} {m!(n-m)!}\mod p^k,p\in prime 。
显然还是不一定有逆元。
我们可以弄成这样：
\frac {\frac {n!} {p^x}} {\frac {m!(n-m)!}{p^yp^z}}p^{x-y-z} \mod p^k
将n!,m!,(n-m)! 中p 的因子都拿出就行了。
那么现在就是要求：\frac {n!} {p^x} \mod p^k
先把其中p 的倍数都拿出。
就是：\frac{n!}{p^x}=(n/p)!*... 。
剩下不是p 倍数的都会以p^k 为周期，还有一些边角料。
\frac{n!}{p^x}=(n/p)!*(\prod_{i,(i,p)=1}^{p^k}i)^{n/(p^k)}(\prod_{i,(i,p)=1}^{n\mod p^k} i)
乱分析一波复杂度：
$T(n) = T(n/p) + p
T(n) = p\log_p n
有题解说是：O(\log_p n) 的，我也不会。
代码
好像有网上大佬说明了复杂度是O(p+ \log^2n)
23
P5249 [LnOI2019]加特林轮盘赌
2019年了还不不取模？卡精度的**题。
先计算出在n 个人时，第i 个人被打中的概率。
然后就变成子问题了。
通过前缀和优化可以做到O(n^2) 。
前缀和比较复杂，建议先写出暴力。
傻逼题要先加起来再减才可以过。
代码
24
P6178 【模板】Matrix-Tree 定理
实际上w 就相当于w 条边而已。
考虑有向图的情况。邻接矩阵就只管单向。而度数就只算一边。外向树算入度，内向树算出度。
以哪个点为根就删掉哪一行哪一列。
不会证明。
代码
25
P3317 [SDOI2014]重建
一道看上去很模板的题目。
我们可以求出所有生成树的边权乘积。但是与模板题不同的是还要计算没有出现的，乘上不出现的概率。我们要处理一下，先将所有都不出现的概率乘上，再令边权w 改为w/(1-w) 。
但是这个时候如果出现1 就会挂掉。所以我用了并查集来特判。但是有人直接卡精度，当w=1 ,令w=1-eps 。。然后就过了，怎么2014年了还不取模啊？
代码
26
P6624 [省选联考 2020 A 卷] 作业题
一道并不模板的题。
注意到和平时的题不一样的是这里的w 是加起来。
显然gcd 要莫反：id=\phi*1 。
在考虑如何计数。
一个朴素的想法：我们考虑一条边的贡献。我们可以缩点，然后单纯生成树计数来计算这条边的贡献。这样的复杂度低至了：O(n^5w) 。但感觉加上剪枝可以拿很多分，但我没写，不清楚。
这个时候发现如果是计算贡献的话，我们不妨考虑构造一个OGF。
我们如果把每条边w 构造成wx+1 。就会发现他们的乘积多项式的一次项就是答案（因为0 次代表拿来计数，1 次代表固定这条边，若干个0 和一个1 ）。
所以我们只需要完成一个一次多项式的Matirx-Tree就可以了。
然而一次多项式的加减乘除都是非常简单的。注意的是这里是\mod x^2 。所以求逆也可以自己手玩快速推出。
这样的时间复杂度为O(n^3w) 。看似并不是很好通过此题。
考虑一个效果非常优秀的剪枝，当小于n-1 条边的时候，显然是无解，可以跳过的。
所以时间复杂度是这样的：
O(n^2w+n^3*\frac{md_{max}(w)} n)=O(n^2w+n^4\sqrt w)
跑不满加3s 时限足以通过。
代码
End
因为文章太长，编辑太卡了，所以换一篇（不知道有没有下一篇）写吧。