考试总结——数学知识[1]

考试总结——数学知识

目录

• • \(\mathit{Math1}\) : 2020.12.24 $\mathit{Math1}$ : [2020.12.24](#1)
• • \(\mathit{Math2}\) : 2020.12.26 $\mathit{Math2}$ : [2020.12.26](#2)
• • \(\mathit{Math3}\) : 2020.12.29 $\mathit{Math3}$ : [2020.12.29](#3)
• • \(\mathit{Math4}\) : 2021.1.2 $\mathit{Math4}$ : [2021.1.2](#4)
• • \(\mathit{Math5}\) : 2021.1.3 $\mathit{Math5}$ : [2021.1.3](#5)
• • \(\mathit{Math6}\) : 2021.1.5 $\mathit{Math6}$ : [2021.1.5](#6)

2020.12.24

• 概括

  1. 贪心缩点
  2. 质因数分解的解题思路（唯一分解定理）
  3. 各种阶乘分解的方法

• T₁ : war

  • 当时有想到对于每个数来说，连接它和它的倍数显然是最优的，但是没有想到正确的枚举顺序以及具体的实现方法。后来不知怎么的居然连 \(30\) 分的 \(Kruskal\) 的暴力都没有打。
  • 但事实证明正解就是借用了 \(Kruskal\) 的思想。
  • 从大到小（顺序不能反过来）去枚举每个因数 \(i\) ，然后将所有包含这个因数的数全部连起来。但是为什么能保证包含这个数的所有数的 \(gcd\) 是 \(i\) 而不是 \(i\) 的倍数呢？这就是为什么不能把枚举的顺序反过来的原因。因为如果两个数的 \(gcd\) 大于 \(i\) ，那么这两个数一定会在枚举到 \(i\) 之前就已经在同一个并查集里面。
  • 感觉正解还是挺难想到的，后来看着题解看了半天也不知道怎么去代码实现，但是写下来之后感觉思路就清晰了许多。从大到小有点像是 \(Kruskal\) 的贪心。

• T₂ : homework

  • 当时就直接打了一个暴力，不知道怎么就过了……（估计是数据太水了……）
  • 当然正解不会是暴力，而是分解质因数计算指数。（原题：[NOIP2009 提高组] \(Hankson\) 的趣味题）
  • 对于某个质因数 \(p\) ，设 \(x,a,b,c,d\) 分解之后 \(p\) 的指数分别为 \(x_p,a_p,b_p,c_p,d_p\) ，那么 \(x\) 一定满足 \(\left\{\begin{matrix} min(x_p,a_p)=b_p \\ max(x_p,c_p)=d_p \end{matrix}\right.\) ，分情况讨论即可。
  • 数论一种比较常见的解题思路：用唯一分解定理分解质因数。只是这道题目要注意一下线性筛只用筛到 \(O(\sqrt{n})\) 即可，然后一个一个质数判断完成之后如果还剩下那么就是唯一一个大于 \(\sqrt{n}\) 的质数了，再次判断即可。

• T₃ : game

  • 其实这道题目思路还是比较好想的，在考场上也想出来了，就是先把所有数全部乘起来，然后全部质因数分解，如果是奇数个的话就乘以这个质因数的逆元就好了。但是不知道为什么当时没有交……
  • 后来按照自己思路打了一遍，发现有几个点超时了，一开始以为是求逆元的问题，后来才发现是分解质因数的复杂度太高了。
  • 一开始是在把所有数乘起来的时候顺便一个一个分解，但是这样就是 \(O(n\sqrt{n})\) 显然会超时。后来求 \(（b\acute{a}i）\) 教 \(（pi\acute{a}o）\) 之后总结几种阶乘分解的方法：
    1. 线性筛，之后直接统计每个质因数出现了多少次： \(\left\lfloor{\frac{n}{p}}\right\rfloor+\left\lfloor{\frac{n}{p^2}}\right\rfloor+\left\lfloor{\frac{n}{p^3}}\right\rfloor+\cdots\) \(O(nlogn)\) （实际上应该是 \(O\left(\frac{N}{ln\:N}\:logN\right)\approx O(N)\) ）
    2. 线性筛的同时记录每个数的最小质因数，然后分解的时候就每次除以当前数的最小质因数，递归分解。\(O(nlogn)\)
    3. 线性筛，然后建树，将质因数作为数的边权，子树的大小就是这个质因数出现的次数，一遍 \(DFS\) 相加即可。\(O(n)\)

go back

2020.12.26

• 概括

  1. 感觉是水题大赛……
  2. 打表找规律
  3. \(exgcd\) 应该会快于费马小定理
  4. 质因数的性质
  5. 借用阶乘分解的思路求累加

• T₁ : sequence

  • 当时没想出来，后来才知道斐波那契数列有一个性质。但是我估计考场上当场推性质并不现实……
  • 后来才知道对于这种题目有一种非常有效的方 \((zh\grave{e}ng)\) 法 \((ji\check{e})\) ——打表找规律。
  • 然后就会发现存在一个因数的关系了

• T₂ : game

  • \(emmmmmm\dots\dots\) 没什么好说的了，就是一个求逆元的板子题。
  • 而且及其真诚，毫无套路……

• T₃ : divisor

  • 一开始还差点被题面绕进去了……事实证明题目所给的性质没什么用

  • 正难则反嘛，换个角度，去枚举每个数 \(i\) ，然后加上 \(\frac{n}{i}\) 就是 \(n\) 以内有多少个数的因数包含 \(i\) ，感觉和阶乘分解的思路有点像。

  • \[\sum_{i=1}^{n}i\:\:\:\:and\:\:\:\prod_{i=1}^{n}i \]

  • 当然，虽然题目的性质对题目来说没有什么帮助，但还是质因数的一个比较重要的性质，用排列组合求所有因数（因为各质因数之间是不会相互影响的）。

go back

2020.12.29（2020说没就没了……）

• 概括

  1. 输入输出文件名居然是大写……
  2. 可以递推组合数再乘上阶乘求得排列数（但是我为什么不直接阶乘分解然后快速幂呢……）
  3. 扩展欧几里得算法（裴蜀定理）

• T₁ : Indexone

  • 感觉就是一道求排列数的板子题
  • 然后……求成组合数直接就爆0了……

• T₂ : Indextwo

  • 怎么说呢，当时没有想到用扩展欧几里得去算就直接模拟了，感觉时间复杂度也是对的，但是就只有10分……
  • 然后用了扩欧之后就没事了……
  • 所以其实像这种能够看出同余关系的都去用扩欧好了。
  • 其实这道题有点独特的地方是如何直观地去理解同余号的右边是一个负数。其实就可以想象成走了 \(x\) 轮以后 \(A\) 比 \(B\) 多走了 \(-k\) 步，其实还是和正数一样的，所以就没有必要特别地去将 \(B-A\) 变成正数。

• T₃ : Indexthree

  • 听说是莫比乌斯反演，然后我就跪了……
  • 还是用容斥吧，但我貌似之前还没有写过容斥的题目……
  • 首先这个题目换一种说法就是求横纵坐标互质的数有多少个。
  • 然后对于每个质数 \(p\) ，它所有的倍数都是非法的，直接把 \(m\) 和 \(n\) 里面 \(p\) 的倍数的个数相乘减去就好。
  • 但是合数都有不只一个质因数，这个时候再加上任意两个质因数乘积的倍数，减去任意三个质因数乘积的倍数，加上任意四个质因数乘积的倍数，减去……
  • 这样就可以借助埃氏筛法顺便求出每个数质因数的个数。最后再枚举一遍，如果当前数有奇数个质因数就减去其倍数，如果有偶数个质因数就加上其倍数。
  • 确实是一种及其美妙的思路（某某：“这不是基础容斥么？”）

go back

2021.1.2（2021说来就来了……）

• 概括：

  1. 质因数分解的解题思路 \((again)\)
  2. \(01\) 排序转成平面路径
  3. 线性求阶乘的逆元（线性求组合数）
  4. 错位排序

• T₁ : supernum

  • 当时在考场上想出了如何判定在 \(B\) 进制下是否有 \(k\) 个 \(0\) ，就是恰好能够整除 \(B^k\) 的数，但是没有想出如何判断……

  • 后来才知道是质因数分解，怎么说呢，感觉在数论里面，质因数分解然后从质因数的角度去讨论是一种很常用的方法。既然已经在考场上想出了关于进制的问题，那么从这道题目中得到的最大的启示就又是质因数分解了。其实考试之前一道同样是质因数分解的题目暴力过了就没改……

• T₂ : road

  • 感觉也是一类比较经典的题目，对于像这种问满足一定条件的 \(01\) 序列的排序方案有多少种。基本的思路都还是转化为平面直角坐标系里面的路径问题，只是根据不同的条件去改变路径的条件。感觉这道题目就比较巧妙，根据条件不能碰到 \(y=x+1\) ，然后用 \((-1,1)\) 到终点的路径方案数来代替不合法的方案数，也是用了一种等效替代法。

  • 但这道题还有一个小技巧，就是线性求阶乘的逆元：先递推求出阶乘并取模，然后求出最后一个阶乘的逆元，再反着递推回去，就可以实现线性求阶乘逆元，感觉以后求组合数都可以直接递推求了。

• T₃ : chess

  • 当时考试的时候把题目都看错了……以为是第一个棋子不能放在第一行和第一列

  • 错位排列感觉又触到我的知识盲区了（当时只是粗略的看了一眼错排），但是这是好事，促使我把错位排序认真地学了一遍。学完之后大呼：“这不就是板子题吗？”

  • 但是这里还是有一个关于错排的一个小小的性质：第 \(n\) 项的平方对 \(n\) 取模之后余数会以 \(n\) 个数为一个循环，并且如果是 \(n\) 的倍数的话余数为 \(1\) 。这个用错排的组合数递推公式还是比较好证明的：

  • \[\sum_{i=0}^n(-1)^i\times C_n^i\times (n-i)!=\sum_{i=0}^n(-1)^i\times \frac{n!}{i!}\Rightarrow \left[ \sum_{i=0}^n(-1)^i\times \frac{n!}{i!}\right]^2\: mod\: n=1\:\:\:\left\{\begin{matrix} i=n &1，-1 \\ i\neq n & 0\end{matrix}\right. \]

  • 然后就只需要递推到 \(mod\) 就行。

  • \(Ps:\) 错排的直接递推公式：

  • \[D[i]=(i-1)\times (D[i-1]+D[i-2]) \]

  • 应该还是比较好证明的吧，\(n\) 个数中，对于 \(i\) ，如果将其放在 \(j\) 的盒子中，那么 \(j\) 有两种选择：要么放在 \(i\) 的盒子里，那么变成 \(D_{n-2}\) 的问题，如果不放在 \(i\) 的盒子里，那么变成 \(D_{n-1}\) 的问题，因为 \(j\) 有 \(n-1\) 种选择，故乘上 \(n-1\)。

  • \(Tip:\) \(D_0\) 应该是 \(1\) （用错排数的递推公式倒着推可以证明，上面的证明公式也能勉强说明——因为 \(n\) 的倍数的排列数模 \(n\) 是 \(1\) ），但是 \(D_1\) 却是 \(0\) 。

go back

2021.1.3

• 概括

  1. 打表找规律
  2. 二进制枚举容斥
  3. 将区间合法数量转化为前缀合法数量
  4. 扩展欧几里得算法求符合条件的通解
  5. **有乘法一定要注意是否开 long long **

• T₁ : crazy

  • 吃了上次的亏，这次自然而然就想出打表找规律的方法了（不得不说，这个确实是一种比较常见的方法）。

  • 然后很容易就发现规律了，直接矩阵快速幂就行了

• T₂ : lucky

  • 事实上考场上想到了容斥原理，但是并没有想到一个比较好的方法去实现。
  • 对于这道题来说，我没掌握的最主要的两个思想就是二进制枚举容斥、前缀和求区间和（当时也是不知道怎么求区间的合法数量）
  • 又学会了两种解题思路，\(nice\)

• T₃ : feed

  • 其实感觉这个扩欧算法还是比较好想的。

  • 如果最适合粥量不是两个勺子最大公约数的倍数就无解。

  • 如果有解的话，就能发现一个显而易见的性质：让容量小的勺子使用的次数尽可能小，所以先 swap 一下把小的放前面，然后将扩展欧几里得算出来的一组特解 \(x\) 的绝对值变得最小，然后将 \(x\) 带回原式就可以算出 \(y\) ，abs 相加即可。

  • 然后呢？\(int\rightarrow long\:long\Rightarrow 100\rightarrow 50\)

go back

2021.1.5

• 概括

  1. 将题目向经典模型转化
  2. 容斥原理求解带限制的盒子放球问题
  3. 根据题目的一些性质去寻找突破口
  4. 前缀和优化 \(DP\) 转移
  5. 压位高精以及输出小细节，压位这么舒服，为什么会有人写高精不压位呢？
  6. 搜索小技巧

• T₁ : dnf

  • 嗯……当时考场上想到了一个递归的思路，就是对于当前的这个技能，存在一个使用的上下限，然后枚举每一种可能，然后递归求解，但是没有打。
  • 考试后打了一遍，发现自己复杂度算错了……\(O(m^n)\) 还不如搜索……
  • 有一个 \(DP\) 的部分分，但是我貌似动态规划也忘了，居然没想到……有点不记得自己有没有写过前缀和优化的 \(DP\) 了，不过确实是非常常用的一种转移优化。
  • 好吧这个题就是一个带限制的盒子放球（相同的球放在不同的盒子里，允许为空，隔板法）问题，用容斥原理写。盒子放球？又是容斥？
  • 为什么说是盒子放球问题？因为 \(N\) 种技能释放 \(M\) 次，就是相当于将 \(M\) 个球放在 \(N\) 个盒子里，每个盒子里有多少个球就是相当于这个技能释放了多少次，用组合数求解即可。
  • 但是这个是带限制的盒子放球问题，求出来的方案中必然会有不合法的方案。那么我们就可以假设盒子 \(i\) 中已经放了 \(L_i+1\) 个球，然后再用组合数求出来的所有方案就都是非法的。
  • 剩下的容斥就和之前一样了，二进制枚举就行。（\(Ps:\) 容斥有可能中途过程中会变成负数，所以最后得到结果的时候要再次取模转正 (ans+mod)%mod）
  • 突然有一种感觉这个题目和之前的那个求在某个区间里面满足要求的数字有多少个的题目(2021.1.3 : T₂ : lucky)有一点像。都有一个特点：带限制的数都非常少。感觉有很多题目都可以根据这样的一些性质去找到一些突破口（因为这种的容斥如果数字大一点（比如27）就直接爆掉了……）。
  • \(Update\:2021/1/17:\) 这不就是多重集组合数的板子题吗？？

• T₂ : euclid

  • 感觉这道题目斐波那契的算法也不是特别难想
  • 但是发现要写高精就是真的恶心……而且发现写完高精还过不了……
  • 好吧，那就只能写压位高精了。貌似从来没有写过压位高精……就连写高精都还是第一次……
  • 其实写压位高精细节 \((k\bar{e}ng)\) 还是挺多的，有很多地方都能卡卡常，经过我的“不懈努力”，这道题终于卡到了 \(200ms\) ……
  • 又多了一个模板，\(nice\) 。
  • \(Ps_1:\) printf("%.9d") 或者 printf("%09d") 都能够在前面补 \(0\) ，用来写压位高精简直完美。
  • \(Ps_2:\) 辗转相除的一个小性质：\(a,b\) 同时整除 \(gcd(a,b)\) ，辗转相除次数仍然相同。

• T₃ : divisor

  • 当时直接暴力拿了 \(30\) 分，后来看了题解发现这解法怎么看起来这么眼熟。思索了一番，这不就是反素数么……
  • 为什么当初学数论的时候没有码一遍反素数的代码……
  • 好吧，言归正传。既然是反素数，那么思路就非常明了了：搜索+剪枝。就当是复习一下搜索吧，好久没有写搜索了，深搜都不会写了……。
  • 时隔“两个多月”再次写搜索确实有一些不同的启发：尽量减少回溯的次数，减少全局变量，用作参数传递就好。
  • 再次用到了之前的那个关于质因数排列组合求所有约数的性质，确实是一脉相承。

go back

总结

• 考完之后真是醍醐灌顶……\(fell\:in\:love\:with\:mathematics\dots\)
• 确实，这一系列的考试能让人学到很多（就像我以前从来没有打过错排、压位高精、容斥什么的）
• 同时也顺便让我复习了之前忘光了的搜索和动归
• 但是最重要的还是去学习每道题目的思想
• 还有掌握一些特别有用小技巧
• 发现自己考试中一些经常会犯的小错误
• 没了，平时多看看自己写的每场考试的总结吧，每次都应该会有不一样的启发

2021年1月10日
——pycr