Q779’s Blog

洛谷P2001 硬币的面值 题解 题目链接：P2001 硬币的面值 题意： 小 A 有 \(n\) 种硬币，现在要买一样不超过 \(m\) 元的商品，他不想得到找钱（多脏啊），同时又不想带太多的硬币，且硬币可以重复，现在已知这 \(n\) 种硬币的价值，请问最少需要多少硬币就能组合成所有可能的价格？ 输入格式： 第一行两个数：\(n, m\)。 下一行，共 \(n\) 个数字，表示硬币的面值。 输出格式： 一行一个数，表示最少需要多少硬币。如果无解请输出 No answer!!!。 数据范围： \(1 \le n \le 2 \times {10}^5,~1 \le m \le 2^{63}\)。 首先如果面额里没有 \(1\) ，那一定无解，否则一定有解。 考虑将所有面额（包括 \(m\)）从小到大排序，依次每个 \(a_i\) 到 \(a_{i+1}\) 的贡献 容易发现，如果我们当前可以覆盖区间 \([1,x]\) 且 \(a_i \le x+1\) ，那我们也能覆盖 \([1,x+ka_i]\) 。 而当 \(x + ka_i + 1\ge a_{i+1}\) 时，我...

拉格朗日反演 注意，本文不是 拉格朗日定理 。 复合与复合逆 定义：形式幂级数 \(F(w) = \sum_{n \ge 0}f_nw^n\) 和 \(G(x) = \sum_{n \ge 1} g_nx^n\) 的复合为 \[ F(G(x)) = \sum_{i \ge 0} f_i(G(x))^i \] 由于 \(G(x)\) 没有常数项，所以即使 \(F(x)\) 有无限多个非零项，这两个函数的复合仍然可以定义。 定义：设 \(F(w) = \sum_{n \ge 1}f_nw^n\) 和 \(G(x) = \sum_{n \ge 1} g_nx^n\) ，如果 \(F(G(x))=x\) ， 那么称 \(F(w),G(x)\) 互为复合逆（反函数），易得 \(F(G(x)) = G(F(x))\) 。 拉格朗日反演 定理：若 \(f(w)\) 是 \(g(x)\) 的复合逆，那么 \[ [x^n]g(x) = \frac{1}{n}[w^{n-1}]\left(\frac{w}{f(w)}\right)^n \] 还有一个推论 \[ [x^n]h(g(x)) = \f...

生成函数与数列 由通项公式求生成函数 博客的表格生成有点问题，直接放个图。 其中 (3)(6) 可用 \(\frac{1}{1-x}\) 泰特展开证明，(5)可用广义二项式定理证明，这里不过多介绍。 由生成函数求通项公式 已知数列 \(\{a_n\}\) 的递推公式，用生成函数求通项公式的步骤如下 把 \(a_n\) 用其他项表示成唯一一个方程，该方程对任意 \(n \in \mathbb{N}\) 都成立，并定义 \(a_{-n}=0~(n > 0)\) 乘上 \(x^n\) ，并对方程两边求和，左边就是 \(\sum_{n \geq 0} a_n x^n=A(x)\) ，右边整理成关于 \(A(x)\) 和 \(x\) 的式子 解出 \(A(x)\) ，此时应是封闭形式 展开为幂级数形式，则第 \(n\) 项的系数即为答案。 对于第四步，一般可以套用上面的表格，否则 如果出现分式，考虑分解成 \(\frac{a}{1 - \rho x}\) 的形式 如果有 \(\ln,\exp\) 等函数，考虑泰勒展开。 如果出现根式，考虑广义二项式定理。 如果出现单独的 \(...

放球问题 题目描述 给定 \(n\) 个（有标号/无标号）的球 放到 \(m\) 个（有标号/无标号）的盒子里 每个盒子（可空/不可空） 注：“可空”表示可以有空的盒子，但不能全是空的盒子。 一些可能会出现的东西： \(A_{m}^n\) ：\(n\) 个元素选 \(m\) 个元素的排列。 \(S(n,m)\) 为第二类斯特林数，表示将 \(n\) 个不同元素划分为 \(m\) 个无区别的非空子集的方案数，有 \[ S(n,0)=[n=0] \\[6pt] S(n,m) = S(n-1,m-1) + mS(n-1,m) \] 解法 给定 \(n\) 个「无标号」的球，放到 \(m(n \ge m)\) 个「无标号」的盒子里，每个盒子「不可空」 解：可以把原问题看作：有 \(m\) 种质量为 \(1,2,\cdots,m\) 的砝码若干，求质量为 \(n-m\) 的方案数。 定义生成函数 \(F(x)\) \[ \begin{aligned} F(x) &= (1 + x^1 + x^2 + \cdots)\times(1+x^2 + x^4 + \cdots) ...

广义二项式定理 二项式定理 \[ (x+y)^n = \sum_{i=0}^{n}\binom{n}{i}x^{n-i}y^{i} \] 其中 \(x,y\in\mathbb{R},~n \in \mathbb{Z_+}\) 。这是高中数学中最令人熟悉的公式了。 广义二项式定理 定义牛顿二项式系数 \[ \binom{\alpha}{r} = \begin{cases} 0&r<0 \\[6pt]1,&r=1 \\[6pt]\frac{\alpha(\alpha-1)\cdots(\alpha-r+1)}{r!},&r>0 \end{cases} \qquad(\alpha \in \mathbb{R},r\in \mathbb{Z}) \] 广义牛顿二项式定理 \[ (x+y) ^ {\alpha} = \sum_{r=0}^{\infty} \dbinom{\alpha}{r}x^{n-r}y^{r} \] 从形式上看和普通的二项式定理是很类似的。 上指标反转公式 设 \(n\) 为正整数 \[ \begin{aligned} (x+y)...

生成函数 学习笔记 这里涉及的记号比较多，建议查阅 博客符号&记号参照表 这篇文章最早写于 2022年9月25日，但是当时基本没怎么理解生成函数。 本文的内容会不断添加更多东西，因为生成函数涉及的内容还是挺多的。 upd. 另外，可以参考 《组合数学》 §2.3 学习笔记（上） 。 生成函数简介 相信有很多初学者都很好奇，这个生成函数到底在干什么，为什么要搞这些东西。 至少我当时也没搞明白，特别是为什么它可以在式子没有意义的情况下还能算出正确答案。 因此本文会从生成函数最基础的部分出发，较为详细的解释什么是生成函数。 例1：有 \(1\) 克、\(2\) 克、\(3\) 克、\(4\) 克的砝码各一枚，能称出哪几种重量？每种重量各有几种可能方案？ 我不打算讲传统解法，直接讲生成函数的解法 我们可以把 \(1\) 克砝码看作 \((1 + x^1)\) ，前者表示不取，后者表示取一个 \(1\) 克砝码 同理，我们可以用 \((1 + x^2)\) 表示不取或取一个 \(2\) 克砝码，用 \((1 + x^3)\) 表示不取或取一个 \(3\) 克砝码等 那么生成函...

洛谷P2000 拯救世界 题解 题目链接：P2000 拯救世界 题意： 为了拯救世界，小 a 和 uim 决定召唤出 kkksc03 大神和 lzn 大神。根据古籍记载，召唤出任何一位大神，都需要使用金木水火土五种五行神石来摆一个特定的大阵。而在古籍中，记载是这样的： kkksc03 大神召唤方法： 金神石的块数必须是 \(6\) 的倍数； 木神石最多用 \(9\) 块； 水神石最多用 \(5\) 块； 火神石的块数必须是 \(4\) 的倍数； 土神石最多用 \(7\) 块。 lzn 大神召唤方法: 金神石的块数必须是 \(2\) 的倍数； 木神石最多用 \(1\) 块； 水神石的块数必须是 \(8\) 的倍数； 火神石的块数必须是 \(10\) 的倍数； 土神石最多用 \(3\) 块。 现在是公元 \(1999\) 年 \(12\) 月 \(31\) 日，小 a 和 uim 从 \(00{:}00{:}00\) 开始找，一直找到 \(23{:}00{:}00\)，终于，还是没找到神石。 不过，他们在回到家后在自家地窖里发现了一些奇怪的东西，一查古籍，哎呦妈呀，怎么不早...

洛谷P1919 【模板】高精度乘法 | A*B Problem 升级版 题解 题目链接：P1919 【模板】高精度乘法 | A*B Problem 升级版 题意： 给你两个正整数 \(a,b\)，求 \(a \times b\)。 输入格式： 第一行一个正整数，表示 \(a\) 。 第二行一个正整数，表示 \(b\) 。 输出格式： 输出一行一个整数表示答案。 数据范围： \(1\le a,b \le 10^{1000000}\) 注意到任意十进制整数都可以写成 \[ a_0\times 1 + a_1 \times 10^1 + a_2 \times 10^2 + \cdots + a_n\times 10^{n} \] 这就是一个 \(n\) 次多项式，不是么。 于是我们可以用 NTT 来优化这个计算，不会 NTT 的可以看这篇 快速数论变换 NTT 注意这本质上是个压位高精，不要忘记最后的进位哦。 时间复杂度 \(\mathcal{O}(n \log n)\) 代码： #include <bits/stdc++.h> using namespace std; #d...

NTT 模数表 传送门： 快速数论变换 NTT 下文记 \(g\) 为最小原根，令 \(P=q\times 2^{21} + 1\) （大写是为了方便记忆）。 常用列表： q P g 476 998244353 3 479 1004535809 3 完整列表： q P g 11 23068673 3 33 69206017 5 39 81788929 7 50 104857601 3 53 111149057 3 54 113246209 7 63 132120577 5 65 136314881 3 66 138412033 5 74 155189249 6 78 163577857 23 80 167772161 3 81 169869313 5 89 186646529 3 95 199229441 3 101 211812353 3 110 230686721 6 119 249561089 3 123 257949697 5 129 270532609 22 131 274726913 3 180 377487361 7 183 38...

快速数论变换 NTT 模板题：P3803 【模板】多项式乘法 (FFT) 建议配合 快速傅里叶变换 FFT 和 阶与原根 两篇文章使用。 在前两篇我们介绍了 FFT 算法如何利用单位根 \(\omega_n^k\) 的性质以快速计算 DFT ，以及原根的性质。 提示：鉴于 FFT 算法的特点，以下默认 \(n\) 为 \(2\) 的幂，即 \(n = 2^m\,(m \in \mathbb{N})\) 。 FFT 那篇可能写的比较复杂，总结一下可以发现，无非就是以下几个重要性质。 \(\omega_n^k\,(0\le k \le n-1)\) 互不相同。 \(\omega_n^{k+\frac{n}{2}} = -\omega_n^k\) 。 \(1+\omega_n^k+\left(\omega_n^k\right)^2+\cdots+\left(\omega_n^k\right)^{n-1}=0\) 。 接着我们在原根的诸多性质中找出几个特别的 对于质数 \(p=qn+1\,(n=2^m)\) ，原根 \(g\) 满足 \(g^{qn} \equiv 1 \pm...

洛谷P1013 [NOIP1998 提高组] 进制位 题解 题目链接：P1013 [NOIP1998 提高组] 进制位 题意： 著名科学家卢斯为了检查学生对进位制的理解，他给出了如下的一张加法表，表中的字母代表数字。 例如： \[ \def\arraystretch{2} \begin{array}{c||c|c|c|c} \rm + & \kern{.5cm} \rm L \kern{.5cm} & \kern{.5cm} \rm {K} \kern{.5cm} & \kern{.5cm} \rm {V} \kern{.5cm} & \kern{.5cm} \rm {E} \kern{.5cm} \\ \hline\hline \rm L & \rm L & \rm K & \rm V & \rm E \\ \hline \rm K & \rm K & \rm V & \rm E & \rm {KL} \\ \hline \rm V &...

快速傅里叶变换 FFT 模板题：P3803 【模板】多项式乘法 (FFT) 题意： 给定一个 \(n\) 次多项式 \(F(x)\)，和一个 \(m\) 次多项式 \(G(x)\)。 请求出 \(F(x)\) 和 \(G(x)\) 的加法卷积，即 \[ [F \cdot G](x) = \sum_{k=0}^{n+m}\sum_{i+j = k} f_ig_j\,x^k \] 输入格式： 第一行两个整数 \(n,m\)。 接下来一行 \(n+1\) 个数字，从低到高表示 \(F(x)\) 的系数。 接下来一行 \(m+1\) 个数字，从低到高表示 \(G(x)\) 的系数。 输出格式： 一行 \(n+m+1\) 个数字，从低到高表示 \(F(x) \cdot G(x)\) 的系数。 数据范围： 保证输入中的系数大于等于 \(0\) 且小于等于 \(9\)。 对于 \(100\%\) 的数据：\(1 \le n, m \leq {10}^6\)。 快速傅里叶变换 (FFT) 是一种用于快速计算 DFT 的算法。 在此之前，我们需要先了解什么是 DFT 。不过理论上来讲，OI 只...