蒟蒻从零开始学习的日记

Archmushroom · 2022-08-23 02:41:51 · 个人记录

本人计算机/软件博三老狗，按理说早过了打各种比赛的年纪，但最近基于一些和大家都不一样的原因，高考出身的本人走上了不知道有什么用的OI之路。基础只有从本研的课程（数据结构、线性代数、组合数学等）中零零散散得到的，学习方法则是接着零散地获得知识（毕竟早不可能有老师系统性地教我了），和刷科目一科目四一样：直接嗯刷题，想不出来就看题解，学习上面的前置知识、算法等，然后像戴佳伟打竞技场一样写小日记（希望不要写出互相矛盾的内容吧！）。我需要记录的内容可能早已刻进大佬们的DNA，大佬看到请小点声笑！

2022年8月22日及以前

斐波那契数列相关：

• 使用矩阵1 1 1 0可以快速推导，其中矩阵乘法用快速幂完成。

• 模p的fib周期最大为6p，甚至可以蒙特卡洛撞出周期（根据生日悖论，平均复杂度仅为\sqrt{p}哦）。

组合数学相关：

• 一大堆组合数一起求（如P2822）可以用杨辉三角，如果要模p，也可以在构造杨辉三角时就边加边模。

• 巨大组合数模p可以用逆元法：模p的意义下除以一个数等于乘它的逆元，a的逆元为a^{p-2}。

• 错位排序D(n)=(n-1)(D(n-1)+D(n-2))

• 卡特兰数h(n)=\frac{C(2n,n)}{n+1}，是括号匹配数，也是进栈出栈问题（P1044）的结果数（上初中的熊孩问过我一道组合数学题，答案就是卡特兰数，现在的初中生，卷，卷啊）

2022年8月23日

碎碎念：

• 求方案数的题通常都要模p，否则有极大可能性溢出，int如果WA了开int64，还WA开高精度。（因此P1002这种水题还搞得我WA一次，气）

2022年9月1日

paper deadline...好久没空刷题了

DP相关：

• 区间DP要看清区间是链状还是环状！环状的话要拆成链，如abcd拆成abcdabc来保证所有可能的链都出现一遍。（困，没认真审题，P1880这种水题还WA得莫名其妙）

2022年9月5日

碎碎念：

• 很愚蠢的WA：某些题要求输出四舍五入后的整数，用完std::round后一定要再强制转换为int！不然大数默认输出科学计数法。

2022年9月8日

数论相关（本来日记的定位是每天小技巧，结果今天重点学了一下数论后变成长篇大论了）：

• 之前说的“巨大组合数C^m_n模p可以用逆元法”的前提是m和n都小于p，大于等于的情况要先用Lucas定理：C^m_n \equiv C^{m/p}_{n/p}*C^{m\%p}_{n\%p} (mod \ p)。（虽然公式本身挺优美，但看到数论就想到当年数论老师拒绝收我当博士生！气！）

• 所谓欧几里德算法就是把gcd(a, b)转化为gcd(b, a % b)，扩展版就是若后者的解为tx, ty，前者的解就是ty, tx - \frac{a}{b}ty。

• 线性同余法x_{i+1} = a * x_i + b (mod\ p)可以试图写成等比数列：(x_{i+1}+\frac{b}{a-1}) = a(x_i+\frac{b}{a-1})。（P3306想了半天，看题解才发现答案竟如此简单！）

• BSGS：求x使a^x\equiv b (mod\ p)，令x=A\lceil \sqrt{p} \rceil - B，其中A和B均小于等于\lceil \sqrt{p} \rceil（注意A不能为0）。然后移项得到a^{\lceil \sqrt{p} \rceil A}\equiv b * a^B (mod\ p)，枚举右边B的情况，左边A的情况，看是否能相等（用unordered_map加速判断）。

• 欧拉定理：a^{\phi(m)} \equiv 1 (mod\ m)，a和m互素，常用于求a^b (mod \ m)，b超级大的情况。扩展欧拉定理用于处理a和m不互素的情况：a^b \equiv a^{b\ mod\ \phi(m) + \phi(m)} (mod\ m)（仅当b \geq \phi(m)时有效！否则直接快速幂算！这是一个坑！）

• 特别大的数可以边读边模，用c=getchar();一位一位读。(容易读出WA，建议直接复制粘贴这里的快读)

2022年9月12日

碎碎念：

• P6162想了半天，看题解竟然是第二类Stirling数，题解中的方法竟然是先暴力打表，然后看出规律......教训一：输入少的题可以先打个表玩玩；教训二：要对各种数列（如错排，Catalan数）的前几项敏感起来，看到就能认出来。

关于生成树：

• Prufer序列是个专门解决生成树的度数问题的好东西，它能得到的两个常用结论：n个节点的生成树个数为n^{n-2}；给定度数为d_1 - d_n的生成树个数\frac{(n-2)!}{\Pi_{i=1}^n (d_i - 1)!} （用于解P2290）。

2022年9月13日

关于二分（从绿题题解学到的，做了好些紫题却至今有做不出来的绿题，足以说明我在xjb学，知识树点得一团糟）：

• 求第k大的数但k规模巨大，可以用二分：考虑数值v，有多少个数比v大？若比v大的数小于k，则说明v太大了；否则说明v太小了。注意可能有误差。

关于DP：

• 有的问题虽然是n维DP，求解时却可以（在空间上）降维，原理是如f[i][j]求出后f[i][j-1]就不再使用，则可以只使用f[i]。Floyd算法可以三维降二维，完全背包（用一些面额硬币拼数额）问题可以二维降一维。

2022年9月17日

关于数论：

• 补充一种大量求逆元（如P3811）的线性方法，适用于模p（质数）：