Q779’s Blog

多项式除法（代数） 学习笔记 注意，本文与「快速数论变换 NTT」无关，是一种代数计算技巧 多项式除法是代数中的一种算法，可以快速手算出一个同次或低次的多项式去除另一个多项式的结果。 事实上，小学学的竖式除法就是该算法在 \(x = 10\) 时的特殊求解方法。 例：考虑计算 \[ \dfrac{x^3-12 x^2-42}{x-3} \] 解： 首先把分子和分母均以降幂排列，缺项补零 \[ \frac{x^3-12 x^2+0 x-42}{x-3} \] 将分子的第一项除以分母的最高次项（即 \(x^3 \div x = x^2\)） 将分母乘以首商，乘积写在分子前两项（同类项对齐）（\(x^2 \cdot(x-3)=x^3-3 x^2\)） 从分子相应项中减去刚刚得到的乘积，得到第一余式 \(-9x^2\) 并写在下方，然后将分子的下一次项拿出来 接下来就把 \(-9x^2 + 0x\) 当作新的被除式，重复前三步 最后得到下式，余式小于除式次数，运算结束 横线之上的多项式即为商，而剩下的 \(-123\) 就是余数，则 \[ \frac{x^3-12 x^...

《计算机网络》 2.1应用层协议原理 研发网络应用程序的核心是写出能够运行在不同的端系统和通过网络彼此通信的程序。 事实上，即使你要为网络核心设备写应用程序软件，也是做不到的，因为他们在网络层及以下层次起作用 这种基本设计，即将应用软件限制在端系统的方法，促进了大量网络应用程序的快速研发和部署。 2.1.1 网络应用程序体系结构 当进行软件编码之前，应当对应用程序有一个宽泛的体系结构计划。 请记住应用程序的体系结构明显不同与网络的体系结构，例如因特网体系结构等 从应用程序研发者的角度看，网络体系结构是固定的，并为应用程序提供了特定的服务集合 在另一方面，应用程序体系结构由应用程序研发者设计，规定了如何在各种端系统上组织该应用程序 在选择应用程序体系结构时，应用程序研发者很可能利用现代网络应用程序中所使用的两种主流体系结构之一 即 客户—服务器体系结构 或 对等（P2P）体系结构。下面我们来详细介绍一下这两种体系结构： 客户—服务器体系结构是常见的体系结构。例如在 Web 应用程序中，有两个相互通信的不同程序， 一个是运行在用户主机上的浏览器程序，另一个是在 Web 服务器主机...

洛谷P2233 [HNOI2002]公交车路线 题解 题目链接：P2233 [HNOI2002]公交车路线 题意： 在幻想郷新建的环城公路上一共有 \(8\) 个公交站，分别为 A、B、C、D、E、F、G、H。 公共汽车只能够在相邻的两个公交站之间运行，因此你从某一个公交站到另外一个公交站往往要换几次车，例如从公交站 \(A\) 到公交站 \(D\)，你就至少需要换 \(3\) 次车。 不过琪露诺的方向感极其糟糕，我们知道从公交站 \(A\) 到公交 \(E\) 只需要换 \(4\) 次车就可以到达，而她却总共换了 \(n\) 次车！ 注意琪露诺一旦到达公交站 \(E\)，她不会笨到再去换车。现在希望你计算一下琪露诺有多少种可能的乘车方案。 输入格式： 仅有一个正整数 \(n\)，表示琪露诺从公交车站 A 到公交车站 E 共换了 \(n\) 次车。 输出格式： 输出一个正整数表示方案数，由于方案数很大，请输出方案数除以 \(1000\) 后的余数。 数据范围： \(4\le n\le10^7\)。 首先从 \(E\) 断环为链，因为走到 \(E\) 以后不会再换车。 此时的...

如何判断网线类型 网线外皮一般都会印有CAT5、CAT5 E、CAT6、CAT7和CAT8等字样 对应的网线类型是五类线、超五类线、六类线、七类线和八类线。 其中，五类线是百兆网线，超五类线和六类线是千兆网线，七类线是万兆网线，八类线是十万兆网线。 （以下改编自真实事件） 有人会说了，为啥我网线是千兆网线，但是网速这么慢呢？ 那就得看你买了多少兆的网络，以及你的路由器啊调制解调器啊是否支持这个速度 如果都达到了配置，那么你的电脑网卡是否支持这个网速呢 如果也ok，那很有可能是路由器不好，家里干扰的东西太多，可以换个路由器试试（

联想拯救者r9000p突然重启 解决方案 玩着玩着自己给重启了，着实令人头大（ 网上搜了一下，实际上是因为玩的时候卡了一下，然后系统以为电脑出问题了，就给重启了 这个解决办法也很简单，关掉故障自动重启即可，步骤如下： 在【系统信息】里找到【高级系统设置】，再找到【高级 > 启动与故障修复】，把里面的自动重启关了就好了。

CF1110H Modest Substrings 题解 题目链接：CF1110H Modest Substrings 题意： 给定两个正整数 \(l, r\) ，称整数 \(x\) 为好的，当且仅当 \(l \leq x \leq r\) 。 对一个由 \(\texttt{0-9}\) 中数字构成的字符串，定义它的权值为这样的非空子串个数： 它不以 \(\texttt{0}\) 开头，且将其看成数字后是好的。 你需要找到一个长度为 \(n\) 的字符串，使得它的权值最大。 如果有多个字符串, 你需要寻找字典序最小的一个。同时，字符串可以有前导零。 输入格式： 三行，每行一个正整数，第一行为 \(l\) ，第二行为 \(r\) ，第三行为 \(n\) 。 输出格式： 两行，第一行表示最大权值，第二行表示权值等于最大权值的最小大数。 数据范围： \(1 \leq l,r \leq 10^{800} , 1 \leq n \leq 2000\) 。 复活后的第一道黑题，有一说一难度确实很高。 首先考虑 \(l,r\) 相差较小的情况，可以考虑对 \([l,r]\) 间的所有数...

OI总结-卡常 这个系列终于来了😎，虽然不是什么卡常带师，但是还是有点东西可以写的。 主要是今天看到了很多奇奇怪怪的优化方法，所以还有一些东西需要慢慢补。 一、输入优化 咕咕咕。 二、输出优化 咕咕咕。 三、位运算优化 这里是最魔幻的，我记得 yukuai26 老师说他们大二的时候会讲一堆奇奇怪怪的优化。 char型数字 转 int型数字 （卡常效果：微小） char x = '1'; cout << (x & 15); // 输出的是：1 原理：一般的写法是 x = x - '0' ，众所周知字符 \(\tt{0}\) 对应的 ASCII 码是 \(48\) 。 而 \(48 = 32 + 16\) ，正好是二进制下第 \(5,6\) 位，而 \((15)_{10} = (1111)_2\) \(x\& 15\) 就是取了一个在 \(48\) 上的增量，这个用法仅适用于数字型。 四、指针优化 访问 a[0] 可以写成 *a （卡常效果：微小） 原理：a[x] 本质上就是 *(a + x) （所以写 x[a] 都可以😶‍🌫️） ...

洛谷P3092 [USACO13NOV] No Change G 题解 题目链接：P3092 [USACO13NOV] No Change G 题意： Farmer John 在市场上为他的农场购买物资。 他的口袋里有 \(k\) 个硬币 \((1 \le k \le 16)\) ，每个硬币的价值在\(1\sim 10^8\) 范围内。 FJ 想进行一连串的 \(n\) 次购买 \((1 \le n \le 10^5)\) ，其中第 \(1\) 次购买需要花费 \(c_i\) 个单位的钱\((1 \le c_i \le 10^4)\) 。 当他进行这一连串的购买时，他可以定期停下来，用一枚硬币来支付自他上次付款以来的所有购买（当然，他使用的这枚硬币必须足够大，以支付所有这些购买）。 不幸的是，市场上的小贩完全没有零钱，所以每当 FJ 使用大于他所欠的钱的硬币时，他都很遗憾地没有收到任何零钱的回报！请计算出最大的金额。 请计算 FJ 在依次进行了 \(n\) 次购买后，最终能得到的最大金额。 如果 FJ 不可能完成他所有的购买，则输出 \(-1\)。 输入格式： 第 \(1\) ...

OI复活记 2022年12月31日 因为 NOIP2022 失利，错失省一，遗憾退役。 但是我又找到了一条适合我的路，因此有了这篇文章。 其实并没有真正复活，因为最多是高三去参加一次 NOIP 了。 但是我现在觉得，作为一个普普通通的人，拿到 NOIP 省一也是光荣的。 是的，我决定休学一年，不仅是找到某种生活的意义，更是一种自我提升的尝试 怎么说呢，总觉得我的人生被疫情彻彻底底的改变了。或者说，被三个阶段的网课改变了。 第一次的网课，我记得很清楚，当时是2020年的上半年，我还没有真正接触竞赛。 那个时候的我还是挺活泼开朗的人，保持着童年的某种纯真吧，因此比较喜欢和别人一起玩 结果突然而来的网课，加上我的“朋友”要么没手机，要么没空，总之就是很孤独的一段时间。 因为没有真正爱上什么东西，所以时间大多在游戏中耗费了，不过那个游戏现在甚至没了。 曾和我一起打了几局游戏的“朋友”，不过是把我当傻子耍，到最后果然只有我荒度了几个月。 从那以后，我的历史道法就再也没追上来过，好在最后中考表现的不算特别烂 我不知道我在暑假真正接触 OI 之前的日子是怎么度过的，也许在拼命补文化课吧。 ...

洛谷P1001 A+B Problem 题解 题目链接：P1001 A+B Problem 题意： 输入两个整数 \(a, b\)，输出它们的和（\(|a|,|b| \le {10}^9\)）。 输入格式： 两个以空格分开的整数。 输出格式： 一个整数。 下面是用 ChatGPT 的回答拼凑出的题解，请放心阅读（不要问我怎么生成的） 喵~，欢迎来到 C++ 的世界！ 喵~，让我们一起开始学习这门优秀的编程语言吧！喵喵~ #include <iostream> // 喵~，这是一条预处理指令喵~。 // 会让编译器在编译本程序之前，把 iostream 这个头文件的内容插入到代码中喵~。 // iostream 文件包含了输入输出流的定义，如 cin 和 cout 喵~。 using namespace std; // 喵~，这行代码告诉编译器，在程序中使用的标准 C++ 库中的名称都属于命名空间 std 喵~。 int main() // 喵~，主函数喵~ { int a, b; // 喵~，定义两个整型变量 a 和 b 喵~ ci...

洛谷P2656 采蘑菇 题解 题目链接：P2656 采蘑菇 题意： q779 和 cxy 要去森林采蘑菇。 森林间有 \(N\) 个小树丛，\(M\) 条小径，每条小径都是单向的，连接两个小树丛，上面都有一定数量的蘑菇。q779 和 cxy 经过某条小径一次，可以采走这条路上所有的蘑菇。由于森林是一片神奇的沃土，所以一条路上的蘑菇被采过后，又会长出一些新的蘑菇，数量为原来蘑菇的数量乘上这条路的“恢复系数” \(c\) ，再下取整。 比如，一条路上有 \(4\) 个蘑菇，这条路的“恢复系数”为 \(c = 0.7\)，则第一~四次经过这条路径所能采到的蘑菇数量分别为 \(4,2,1,0\) 。 现在，q779 和 cxy 从 \(S\) 号小树丛出发，求他们最多能采到多少蘑菇。 输入格式： 第一行两个整数，\(N\) 和 \(M\)。 第二行到第 \(M+1\) 行，每行四个数，分别表示一条小路的起点、终点、初始蘑菇数和恢复系数。 第 \(M+2\) 行，一个整数 \(S\)。 输出格式： 一行一个整数，表示最多能采到多少蘑菇，保证答案不超过 \(2^{31}-1\)。 数据范围...

Linux 目录下的 . 和 .. 文件 在使用 ls -a 命令的时候，我们会发现任何目录下都有 . 和 .. 两个文件。 事实上，Linux 系统的目录下一定会有 . 和 .. 两个文件， 只有这两个文件的目录就是空目录。 这两个文件可以被归纳为特殊文件，但是其本质和普通文件没有区别，只是名字独特而已。 其中 . 文件是用于指代目录本身，而 .. 是用于指代目录的上级（像不像每个节点都有自环的一棵树） 仔细想想也是，我们有 cp -r source/. dest 和 cd .. 这种指令，对吧。 阅读参考文献[1]，个人认为这种设计是为了某种完整性或者说统一性， 比如我们建混合图的时候不是无向边和有向边分类建，而是把无向边看作两条有向边。