Q779的博客

洛谷P1919 【模板】高精度乘法 | A*B Problem 升级版题解题目链接：P1919 【模板】高精度乘法 | A*B Problem 升级版题意：给你两个正整数 \(a,b\)，求 \(a \times b\)。输入格

2024-01-30 OI

算法数学多项式

NTT 模数表传送门：快速数论变换 NTT 下文记 \(g\) 为最小原根，令 \(P=q\times 2^{21} + 1\) （大写是为了方便记忆）。常用列表： q P g 476 998244353 3 47

2024-01-30 OI

数学多项式

快速数论变换 NTT 模板题：P3803 【模板】多项式乘法 (FFT) 建议配合快速傅里叶变换 FFT 和阶与原根两篇文章使用。在前两篇我们介绍了 FFT 算法如何利用单位根 \(\omega_n^k\) 的性质以快速计算 DF

2024-01-30 OI

算法数学多项式

洛谷P1013 [NOIP1998 提高组] 进制位题解题目链接：P1013 [NOIP1998 提高组] 进制位题意：著名科学家卢斯为了检查学生对进位制的理解，他给出了如下的一张加法表，表中的字母代表数字。例如： \[ \de

2024-01-28 OI

算法数学

快速傅里叶变换 FFT 模板题：P3803 【模板】多项式乘法 (FFT) 题意：给定一个 \(n\) 次多项式 \(F(x)\)，和一个 \(m\) 次多项式 \(G(x)\)。请求出 \(F(x)\) 和 \(G(x)\) 的加法

2024-01-27 OI

算法数学多项式

阶与原根前置知识：欧拉定理、费马小定理、拉格朗日定理。模板题：P6091 【模板】原根题意：给定整数 \(n\)，求它的所有原根。为了减小你的输出量，给出输出参数 \(d\)，设 \(n\) 的所有原根有 \(c\) 个，从小到

2024-01-25 OI

算法数学

拉格朗日定理拉格朗日定理（数论）设 \(p\) 为素数，对于模 \(p\) 意义下的整系数多项式 \[ f(x) = a_n x^n+a_{n-1} x^{n-1}+\cdots+a_0 \,(p \not\mid a_n) \] 的同

2024-01-25 OI

数学

洛谷P2210 Haywire 题解题目链接：P2210 Haywire 题意： Farmer John有 \(N\) 只奶牛（\(4 \leq N \leq 12\)，\(N\) 是偶数）。他们建立了一套原生的系统，使得奶牛与他的朋

2024-01-24 OI

算法图论 DP

小蓝书 17.4 题解传送门：小蓝书 17.4 第一部分例题例4 由于书上例1,2,3都是基础概念，所以直接从例4开始讲。某 \(15\) 座城市，他们之间的航线分数三家航空公司。一直无论哪家航空公司停飞，旅客总还能从任意城市飞往其

2024-01-24 笔记

数学咕咕

小蓝书 17.4 小蓝书上 17.4 主要讲了讲树的一些性质树，想必大家都很熟悉了，所以这篇文章不打算再讲，我们主要来讲例题。不过有个东西可以提一下，小蓝书提到了闭链的概念，定义为一条链的开头与结尾相同。这不意味着闭链就是环，因为环强

2024-01-24 笔记

数学

自适应辛普森法模板题：P4525 【模板】自适应辛普森法 1 题意：试计算积分 \[ \displaystyle{\int_L^R\frac{cx+d}{ax+b}\,\mathrm{d}x} \] 结果保留至小数点后 \(6\) 位

2024-01-23 OI

算法数学微积分

小蓝书 17.3 \(k\) 部图：若图 \(G=(V,E)\) 的点集 \(V\) 可以被分解为 \(k\) 个两两不交非空子集的并，并且没有任何一条边的两个端点都在同一个子集中，则称 \(G\) 为 \(k\) 部图，记作 \(G

2024-01-23 笔记

数学