『初丶晴』的小窝

8dfed501bcaa90b15714e3bdc993ce4cd992d53dfa3b2cc635d9ae939003f1dd5c23e709214466c64cc05b7d50a03346992d005cdfc2bcbaec37fa9f455272442483f93ab190c61251ba8e742953e04eb1cfad43c738ad42f0e3eee631144324301e4c4bce11eddc610158ddbf5c9d1e59ec2b9b5a667ffb93a0b7e0f50266a7fdbe09a4fae4ccec15e8ba81569c2581a03b4553feb6bc04b57ea0ebc77bb6654f6e3551d4f146128dc3d52add42f5a4bd15433140f07b3741a7790b289a6dbb4915087ff7851c382bf7c953562c5d32b5e8bbb8032b602062e17dbb799dd5b289140a9435960d9ea478def81b909fdfca9db0aff6ecd4abb ...

8dfed501bcaa90b15714e3bdc993ce4cd992d53dfa3b2cc635d9ae939003f1ddcc424989075bdf424c5cb8f31000e57a9db4b0b97597d7d935821682bf3633fffd00d5c963e68ad05871d197e65a0132dadf2a7da1356922f7c275e3b359c44cb7b65c7c78a02d14046e0f1ab8715337704d1956c6d7447c571ef89d723318adb97b9665fb81595b7f57c330c2920af6c78528b335bf75db8fe729dc49149cb856f958b67a84d3fceff852609b47bcecb797087fbc1976104148e592639cd70216f43f32a5950efe3e18c076da405e4ef8a7015c94898757b0c60db3eb5824c33d7f8193666675b613d59614f9500a5d5c1945b20d06ef851 ...

卷首语 岁月沧桑。生命难测。 未来的路，是曲折还是平坦？是泥泞还是山坡？是一种难解的迷。 别去猜想，别去思考。今天的事情已经够多了。不必去为明天而忧虑。愁绪会让红颜苍老。开心才是生活的最佳选择。坎坎坷坷风雨之行。曲曲折折红尘之路。都是人生中必须要历经的。 如果人生都是阳光灿烂，没有风雨。就失去了意义。只有在荆棘之中才会懂得活着的不易。 书目索引 《解忧杂货店》[日]东野圭吾（2023-07-30） 读书笔记《解忧杂货店》 《活着》余华（2023-10-01） 读书笔记《活着》

Problem.1 等比数列求和 题目标签：分治、数学 题目大意 对于有 \(x+1\) 项的等比数列 \(A=a^0+a^1+\cdots+a^x\)，求 \[ (\sum\limits_{i-1}^xa^i)\bmod p \] 数据范围 \(1\leq a_i,x\leq 10^{18},1\leq p\leq 10^9\)。 解题思路 考虑分治。 对于指数区间 \([0,m]\)，令 \(m'=\dfrac{m+1}{2}-1\)。考虑对 \([0,m']\) 和 \([m'+1,m]\) 分治进行处理。 对于区间 \([0,m']\)，求得 \(U=\sum\limits_{i=0}^{m'}a^i\)。 对于区间 \([m'+1,m]\)，可以同时通过分治计算 \(V=a^{m'+1}\)，然后进行分类讨论： 若 \(m\) 为奇数，则有偶数项，此时区间和为 \[ U+UV \] 若 \(m\) 为偶数，则有奇数项，考虑先处理前 \(m-1\) 项，最后加上第 \( ...

多项式乘法与快速傅里叶变换(FFT) 一、前置知识 本节介绍多项式前置知识、复数及单位根的相关内容。 1.1   多项式 设 \(A(x)\) 为一个 \(n\) 次多项式，则可以表示为 \[ A(x)=\sum\limits_{i=0}^n a_ix^i \] 其中，\(a_i\) 为多项式第 \(i\) 项的系数。 一个多项式在 \(x_0\) 处的取值 \(A(x_0)\) 为其在 \(x_0\) 上的一个点值。 一个 \(n\) 次多项式可以用 \(n+1\) 个点值表示出来。由 \(n+1\) 个对应位置上的点值能唯一表示一个多项式。 形式化地，一个多项式可以由 \(n+1\) 个点 \((x_i,y_i)\) 唯一确定，其中，\(y_i=\sum\limits_{j=0}^n a_jx_i^j\)。 1.2   复数 设 \(a,b\in \mathbf R\)，令 \(i^2=-1\)，称形如 \(a+bi\) 的数为复数。其中，称 \(a\) 为复数的实部，\(b\) 为复数的虚部。\(a=0\) 的数称为纯虚数。 在二维平面中，用横 ...

微积分学习笔记 - 05 三角恒等变换 进入 传送门，阅读刊载在专栏《微积分学习笔记》下的全部文章。 九、三角恒等变换 本节作为数学基础，为后面章节做铺垫且与微积分暂时无关。三角公式只涉及三个三角函数 \(\sin,\cos,\tan\)，剩余三个三角函数 \(\cot,\sec,\csc\) 的公式可自行扩展，因不常用而略去。 本节公式大多为高一内容，稍作补充完善。基本公式不作证明，拓展内容部分有公式证明。 9.1   和角公式 下面给出三角函数的和角公式。 和角公式   给定两角 \(A,B\)，则有： \[ \begin{aligned} \sin(A+B)&=\sin(A)\cos(B)+\cos(A)\sin(B)\\ \cos(A+B)&=\cos(A)\cos(B)-\sin(A)\sin(B)\\ \tan(A+B)&=\dfrac{\tan(A)+\tan(B)}{1-\tan(A)\tan(B)} \end{aligned} \] 9.2   差角公式 下面给出三角函数的差角公式。 差角公式   ...

组合数学学习笔记 02 二项式反演 进入分类索引，阅读该专题下的往期笔记。 二、二项式反演 2.1   基本形式 对于定义在域 \(X\) 上的实值函数 \(F(n)\) 与 \(G(n)\)，若由如下递推关系 \[ G(n)=\sum\limits_{i=0}^n\binom n i F(i) \tag{1} \] 得到 \(G(n)\) 关于 \(F(i)\) 的表达式，则可以通过如下的递推关系通过 \(G(i)\) 反解 \(F(n)\)： \[ \boxed{F(n)=\sum\limits_{i=0}^n\binom n i (-1)^{n-i} G(i) \tag{2}} \] 上述通过 \(G\) 反解 \(F\) 的过程称为二项式反演。 要证明二项式反演，下面引入两个二项式系数引理。 引理 1   \(\dbinom n i\dbinom i k=\dbinom n k \dbinom {n-k} {i-k}\)。 证明   考虑组合意义：在 \(n\) 个元素中先取出 \(i\) 个元素，再在 \(i\) 个元素中取出 \(k ...

组合数学学习笔记 01 二项式定理与二项式系数 进入分类索引，阅读该专题下的往期笔记。 本章节介绍二项式定理与相关推论定理，在组合数学中有重要作用。 一、二项式定理与二项式系数 1.1   二项式定理 定理 1（二项式定理）   设 \(n\) 是正整数。对所有的 \(x\) 和 \(y\)，有 \[ (x+y)^n=\sum\limits_{k=0}^n\binom nk x^{n-k}y^k\tag 1 \] 证明   考虑把 \((x+y)^n\) 展开，结果有 \(2^n\) 项，每一项都可以写成 \(x^{n-k}y^k\) 的形式。对于每个形式，相当于在 \(n\) 个因子中选择 \(k\) 个选择 \(x\)，故其系数为 \(\binom n k\)​。 1.2   组合相关推论 如果对于二项式定理，取 \(y=1\)，则有如下特殊形式。 定理 2   设 \(n\) 为正整数。对于所有的 \(x\)，有 \[ (1+x)^n=\sum\limits_{k=0}^n \binom n k x^k\tag{2} \] 证明略去。 ...

微积分学习笔记 - 04 指数、对数、双曲函数的导数与极限 进入 传送门，阅读刊载在专栏《微积分阅读笔记》下的全部文章。 六、指数函数与对数函数的导数 本节通过对自然常数 \(\mathrm{e}\) 的探究推出指数与对数函数的导数。请务必在阅读本节前了解指数与对数的基本运算性质。 6.1   \(\mathrm{e}\) 的定义与相关极限 \(\mathrm{e}\) 的定义   对于极限，定义 \[ \mathrm{e}=\lim\limits_{h\to 0^+}(1+h)^{\frac1h} \] 关于它的求解与证明暂时略去。通过上述极限可以推出许多性质。 考虑极限 \[ L=\lim\limits_{n\to \infty}(1+\dfrac rn)^n \] 令 \(h=\dfrac rn\)，这样 \(n=\dfrac rh\)，对上述极限变形，有 \[ L=\lim\limits_{h\to 0^+}(1+h)^{\frac rh}=\lim\limits_{h\to 0^+}((1+h)^{\frac 1h})^r=\mathr ...

微积分学习笔记 - 03 隐函数求导 进入 传送门，阅读刊载在专栏《微积分阅读笔记》下的全部文章。 五、隐函数求导 这一节与其他节相关很少，但后面也要经常用到，所以只好单拎出来。 5.1   隐函数求导 考虑两个导数 \[ \dfrac{\mathrm{d}}{\mathrm{d}x}(x^2) \quad,\quad \dfrac{\mathrm{d}}{\mathrm{d}x}(y^2) \] 前者显然为 \(2x\)，但后者却不一定。这主要取决于变量 \(y\) 与变量 \(x\) 间的变化关系。 那怎样求它的导数呢？参考链式求导法则，变量 \(x\) 的改变会导致变量 \(y\) 的改变，而变量 \(y\) 的改变又会导致 \(y^2\) 的改变。 令 \(u=y^2\)，则 \(\dfrac{\mathrm{d}u}{\mathrm{d}y}=2y\)，则： \[ \dfrac{\mathrm{d}}{\mathrm{d}x}(y^2)=\dfrac{\mathrm{d}u}{\mathrm{d}y}\dfrac{\mathrm{d}y}{\ ...