Claudy Forrest

> > （不过确实很想吐槽现在的目录已经很臃肿了，如果开一个重新调整（数学部分的）目录的 issue 或者 pr 会被喷吗……） > > 既然您总在说一些“我无法认同”等，那我觉得目前这个样子确实已经很好了。希望早日能尽快完成更新。 > > 至于诸如“目录臃肿”等，提出的诸多缺陷啥的，我相信未来的强手还是层出不穷、后浪推前浪的。即使你不写、我不写，也有的是人写。所以我是不怕缺陷的。即使当下有再多的缺陷，迟早也会有更正的一天。 > > 不过，如果您愿意写，那当然是多多益善了。不仅不会被喷，还应当鼓励。如果有一天真的彻底没人写了，那才是可怕的事情。如果不写，就永远不会进步，只会意味着圈子彻底地冷掉。没有活人的领域还能叫领域吗？还是希望大家勇敢的去写。 所以您的建议是在线性代数部分增加中国剩余定理和 lagrange 插值？

> 我有个问题，就是为啥这个 pr 要整这么大而不是拆成很多个部分🧐因为修改内容会环环相扣吗 现在这个太大了不是很利于 review。 这个有点计划赶不上变化了，确实是我经验不足的锅。 因为抽象代数部分本身只有一个文件，然后需要裂成三个文件（基本概念、群论、环论），然后原本的群论文件夹中还有名为置换群实为 Polya 计数的文件，我寻思拖出去但是原封不动也不好，就也顺手改了，但是这又牵涉到置换和排列那部分内容不完善，不能适应别的部分的需求，我也顺手改了。结果就是现在这样。 现在问题是，本 pr 已经既成事实，有什么办法能分离这些 commitment 吗？比如说，可以分成三个 pr： - 置换和排列 - Polya 计数 - 抽象代数部分 还是我只要把文件 copy 到别的 batch 重新开 pr 就可以了？

> > 尽管可能 OI Wiki 现有页面的确没有关于 Lagrange 插值的专门介绍（但是有复杂度更低的快速插值）。 > > 实际上是有的，不仅有 Lagrange 插值还有 Newton 插值，只不过内容比较少而已。 > > https://oi-wiki.org/math/numerical/interp/ > > > **[插值 - OI Wiki](https://oi-wiki.org/math/numerical/interp/)**OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛 谢谢提醒，最近翻目录也翻到了这个。会在中国剩余定理的相关位置加一个它的内链的。 插值 -...

@24OI-bot lint please

本页面的域论内容已经写好了，欢迎大家 review！ 本 PR 做了如下修改： - 增加了域论内容 - 域的扩张理论 - 分圆域、分圆多项式 - 有限域，附参考实现 - 域扩张的应用 - 在抽象代数其他页面增加向域论页面的内链 - 修改了目录文件

@zjkmxy 您好，谢谢您的建议。 对于前两条，我很赞同您的意见，会尽快修改。 对于第三条，分母的 $1-2x$ 没有消失，只是在计算了余式（remainder）之后只保留了常数项。因为此处的推理说明余式是 $f(n)(1-2x)$，所以只要考虑常数项就可以了。 对于您的新的理解方式，我想请教一下，您的这种思路对于更广泛的情形是否也是成立的？比如说，在问题 [CF1103E](https://codeforces.com/problemset/problem/1103/E) 中，标答需要在 $\mathbf Z_{2^{58}}$ 上对 $\Phi_5(x)$ 做「扩张」，并利用得到的原根进行快速 Hadamard-Walsh 变换。 我写这个小节的本意并不是仅讨论斐波那契数列的计算，而是希望借此讨论一种方法，能够对任意模数做类似扩域的处理。但是我不想引入诸如 CF1103E 这种看起来就很复杂的问题，所以还是借着斐波那契数列的计算做了一些讨论。我主要是觉得，我所给出的讨论，从扩域的想法上看是自然的，操作在数学上也是合法的（OI Wiki 在 [此处](https://oi-wiki.org/math/poly/fwt/#%E4%BE%8B%E9%A2%98) 有这个例题的讲解，但是用的语言很粗糙，在数学上并不严格），而且清晰地给出了这类方法的适用范围，即需要一个不依赖于除法或者除法造成的影响在当前模数下可控的计算过程。 不知道您对这类一般性的问题有没有更好的想法？ 另外，我觉得您给的思路中，要把每个步骤展开说明，可能也不是容易的。例如，\varphi(P) = \varphi(P mod x^2-x-1)...

@zjkmxy 您好，多谢您的回复，十分受教。 我之前提到的问题还是存在的：是否可以不依赖于环的结构简单说明 $\pi' \circ i = 0$？这个和后续的推演都没有关系，而且看起来十分显然。但是它在引入了环的结构之后看起来比单纯在群里做证明，要简单得多？ 我觉得您的想法对于解决斐波那契数列的问题是很好的，但是有些过于深刻了。在原 issue 的讨论中，有 [评论](https://github.com/OI-wiki/OI-wiki/issues/5356#issuecomment-1885161742) 提及到没有必要引入模论，这也是为什么在写的时候直接从环论跳到了域论。 说起来写这个抽代的简介，内心一直就是十分矛盾的：既觉得算法竞赛中没有考这玩意的，根本就没有必要写，又觉得很多东西放在这个背景下可能会更清晰一些。所以，在内容上一直在选取可能会和算法竞赛更相关的部分，也希望通过更方便没有受到严格代数训练的选手阅读的方式来表达，哪怕牺牲一些数学上的深刻。这也是为什么没有引入商群的万有性质，也没有写 Galois 理论（尽管我都写完了可分正规扩张）。希望您能理解这种权衡。 这也是我为什么觉得直接讲对环做「扩张」会更好一些的原因，尽管它在数学上可能不是好的思路。本质上只是想说，这些域扩张的思路如果不需要做过多除法，也可以在很多环上成立。当然您指出，这个可能和取模视作函子的性质有关。但是我的原意是，你尽可以做这样环上的扩张，只要你写出一个不依赖于除法的表达式，再取模就可以了。这个想法尽管在数学的角度走了很多弯路，但是直接理解上没有难度？而且对于斐波那契数列、CF1103E，甚至更广泛的情景都适用？ 谢谢！

@zjkmxy 谢谢您的回复！ 我的第一点可能没有表述清楚。我的意思是检查 $\pi'\circ i=0$ 这个事实可能还是需要依赖于环的结构，我没有提及后面的万有性质的那部分。 不过确实您的代数课程的观点还是很高的。假想一下，如果我的第一本代数课本是范畴写起的，我可能就弃疗代数了。感觉对于我这种脑子没那么灵光的，范畴还是适合掌握一些基本的具体的结构之后再理解起来会更容易些。所以可能是在学习模和代数拓扑的时候，才遇到了比较多的范畴的概念。 至于环扩张的概念，我在 [脚注](https://deploy-preview-5913--oi-wiki.netlify.app/math/algebra/field-theory/#fn:ring-extension) 中其实给了个 [维基页面](https://en.wikipedia.org/wiki/Subring#Ring_extensions) 中的定义，这可能是域扩张的概念在环中最直接的推广。当然我承认，可能实际可以处理的情形，都是整扩张的类型，因为多项式不是首一的可能会引起很多麻烦。如果您觉得合适，我在同一个脚注里也提一下整扩张的概念？

从 [读入、输出优化](https://oi-wiki.org/contest/io/#%E4%BD%BF%E7%94%A8-fread-%E4%B8%8E-fwrite-%E5%AE%9E%E7%8E%B0) 抄了份快读、快写的代码，卡一卡评测机波动就 [过了](https://www.luogu.com.cn/record/227284219)。考虑到示例代码的可读性问题，这种简单的卡常不会放入示例代码。 如果有不需要卡常能通过本题的方法，欢迎重开本 issue。

可能需要考虑修改现有的 [自动机](https://oi-wiki.org/string/automaton/) 页面。dp 套 dp 的部分可能需要挂一个内链到相关页面（如果 #6318 合了的话）。 至于完善之后的自动机页面是否仍然放在字符串分类下，这个取决于补充的内容为何，可能需要进一步讨论。之前的页面放在字符串分类下是合理的，因为它相当于提供了字符串涉及的很多自动机的概述。