Q779’s Blog

《组合数学》 §2.1 学习笔记 2.1.1 ~ 2.1.2 略。 定理 2.2.3 定义斐波那契数列 \[ f_n = \begin{cases} 0 & n = 0 \\[8pt]1 & n = 1 \\[8pt]f_{n-1} + f_{n-2} & n \ge 2 \end{cases} \] 当 \(n \ge 0\) 时有 \[ f_n = \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left(\frac{1 - \sqrt{5}}{2}\right)^n \] 证明略。 例 2.1.4 略。 定义 2.1.5 称数列 \(\{h_n\}_{n=0}^{\infty}\) 满足 \(k\) 阶常系数线性齐次递推关系，若对所有的 \(n \ge k\) ，有 \[ h_n = a_1h_{n-1} + a_2 h_{n - 2} + \cdots + a_k h_{n - k} \] 其中 \(a_k \ne 0~(k \ge 1)\) ...

《组合数学》 §1.4 学习笔记 前言：本章节标题叫组合恒等式，那我就一个证明都不写了。 定理 1.4.1 （二项式定理） 参考 广义二项式定理 （什么垃圾作者怎么这么推荐的？原来是我啊那没事了） 性质 1.4.2 设 \(n \ge k \ge 0\) ，则 \[ \binom{n}{n-k} \] 性质 1.4.3 设 \(n \ge 0\) ，则 \[ 2^n = \sum_{k=0}^n\binom{n}{k} \] 性质 1.4.4 设 \(n \ge 1\) ，则 \[ 0 = \sum_{k=0}^n(-1)^k\binom{n}{k} \] 推论 1.4.5 设 \(n \ge 1\) ，则 \[ \sum_{2k + 1}\binom{n}{2k+1} = \sum_{2k} \binom{n}{2k} \quad(k > 0) \] 性质 1.4.6 （Vandermonde 恒等式） 设 \(n,m \ge 0\) ，则 \[ \binom{m+n}{k} = \sum_{i=1}^k\binom{m}{i}\binom{n}{k-i} \] 推论 1...

《组合数学》 §1.3 学习笔记 1.3.1 ~ 1.3.7 和 1.3.11 ~ 1.3.16 这部分请参考 小蓝书 16.1 。书上例题也都比较经典/简单，所以不写了 例 1.3.8 把集合 \(\{1,2,\cdots,n\}\) 划分 \(b_1\) 个 \(1\)–子集，\(b_2\) 个 \(2\)–子集，……，\(b_k\) 个 \(k\) 元集，其中 \(\sum_{i=1}^k i b_i = n\) ，求方案数。 解 \(b_i\) 个子集之间没有顺序，那么就是 \[ \frac{\dbinom{n}{1,\cdots,1,2,\cdots,2,3,\cdots,3,k,\cdots,k}}{b_1!b_2!\cdots b_k!} \] 其中 “\(\cdots\)” 有多少个取决于 \(b_i\) 。 注 1.3.9 进一步，一个 \(n\)–集合的全体划分数为 \[ \sum_{b_1 + 2b_2 + \cdots + nb_n = n} \frac{n!}{b_1!b_2!\cdots b_n!(1!)^{b_1}(2!)^{b_2}\cdots(n...

《组合数学》 §1.2 学习笔记 前言：本文有很多 \(\leqslant\) 符号，均表示偏序关系。小于等于则使用 \(\le\) 。（自己定的规则，其实可以混用） 定义 1.2.1 设 \(X\) 是一个非空集合， \(P\) 是定义在 \(X\) 上的具有自反性、反对称性及传递性的二元关系， 则称 \(\mathbf{P} = (X,P)\) 为一个偏序集。在不引起混淆的情况下，又是直接称 \(X\) 是一个偏序集。 符合上述性质的关系称为偏序关系。 通常用 \(x \leqslant y\) 来描述 \(X\) 中的元素 \(x,y\) 满足偏序集 \((X,P)\) 中 \(P\) 所规定的关系， 即 \((x,y) \in P\) 记为 \(x \leqslant y\) ，这样偏序集 \((X,P)\) 也可写成 \((X,\leqslant)\) 。 根据 “\(\leqslant\)” ，自然地定义 \(X\) 上的二元关系 “\(<\)” ：\(x < y\) 表示 \(x \leqslant y\) 且 \(x \ne y\) 。 例 1.2.2...

《组合数学》 §1.1 学习笔记 前言：开新坑，但是这个坑比其他的好填。 定义 1.1.1 组成集合的对象称作元素。 定义 1.1.2 多重集是元素可以重复出现的集合。某个元素 \(a_i\) 出现的次数 \(n_i~(n_i = 0,1,\cdots,\infty)\) 称作元素的重数。 通常把含有 \(k\) 种不同元素的多重集 \(S\) 记作 \(\{n_1\cdot a_1, n_2\cdot a_2,\cdots,n_k\cdot a_k\}\) ，也记作 \(\{a_1^{n_1},a_2^{n_2},\cdots,a_k^{n_k}\}\) 。 定义 1.1.3 给定集合 \(A\) ，称集合 \(A\) 中的元素个数为集合 \(A\) 的基数，记作 \(|A|\) 。若 \(|A|=n\) ，称 \(A\) 为一个 \(n\)–集合 定义 1.1.4 给定集合 \(A\) ，称 \(A\) 所有子集构成的集合为集合 \(A\) 的幂集，记作 \(P(A)\) 。 例 1.1.5 图 \(G=(V,E)\) ，\(V\) 称作顶点集，\(E\) 称作边集，其他略。...

洛谷P9529 [JOISC2022] 一流团子师傅 题解 题目链接：P9529 [JOISC2022] 一流团子师傅 题意： JOI 君是一位专业的团子师傅。在 JOI 君的店里，团子的颜色很有讲究。一共有 \(N\) 种颜色，编号为 \(1,2,\dots,N\)。 一流团子串是 JOI 君的店里的招牌食品。制作一个一流团子串，需要将 \(N\) 个颜色不同的团子串在一根竹签上。 对于每一种颜色，JOI 君都制作了 \(M\) 个这种颜色的团子。因此，JOI 君总共有了 \(NM\) 个团子。这些团子被编号为 \(1,2,\dots,NM\)。使用这些团子和 \(M\) 根竹签，JOI 君希望串出 \(M\) 个一流团子串。 为了避免在颜色上犯错误，JOI 君将会启用他的团子检测器。如果 JOI 君输入一些团子的编号，团子检测器会返回使用这些团子能制作的一流团子串的个数的最大值。当然，前提是充分使用竹签。 JOI 君希望能通过使用若干次团子检测器将 \(NM\) 个团子分为 \(M\) 组。其中，每一组包含 \(N\) 个团子，且每种颜色的团子恰有一个。 JOI 君想在使用...

CF1114E Arithmetic Progression 题解 题目链接：Arithmetic Progression 题意： 这是一道交互题。 有一个长度为 \(n\) 的序列 \(a\)，保证它从小到大排序后是个等差数列。 你不知道这个序列长什么样，但你可以询问： \(\texttt{? i}\) 表示询问 \(a_i\) 的值； \(\mathtt{>\ x}\) 表示询问序列中是否存在严格大于 \(x\) 的数。 你可以问不超过 \(60\) 个询问。 现在，你需要求出这个等差数列的首项和这个等差数列的公差。 数据范围： \(2\le n\le 10^6,~0\le a_i\le 10^9\)。 注意到操作二可以让我们二分出序列的最大值，记为 \(a_n\) （就当题目的序列没有名字好了）。 那么接下来的询问只能问询问一了，因为询问二根本问不出什么东西，这不明摆着让我们乱搞么？ 考虑把所有剩下的询问都用于操作一，记询问得到的数为 \(x_1,x_2,\cdots,x_k\) 。由于 \[ d\mid\gcd\{a_n-x_1,\,a_n-x_2,\,a_...

CF1592F1 Alice and Recoloring 1 题解 题目链接：Alice and Recoloring 1 题意： 本题与 CF1592F2 的差异在于花费不同。 给定一个 \(n\) 行 \(m\) 列的目标矩阵，矩阵元素只有 W 或 B ，并且你有一个初始矩阵，元素全为 W 。 现在你可以矩阵实施以下操作： 使用一块钱，选定一个包含 \((1,1)\) 的子矩阵，把矩阵中的元素全部反转（ W 变 B ， B 变 W ）。 使用两块钱，选定一个包含 \((n,1)\) 的子矩阵，把矩阵中的元素全部反转。 使用四块钱，选定一个包含 \((1,m)\) 的子矩阵，把矩阵中的元素全部反转。 使用三块钱，选定一个包含 \((n,m)\) 的子矩阵，把矩阵中的元素全部反转。 现在需要你求出把初始矩阵变为目标矩阵最少需要几块钱。 输入格式： 第一行两个正整数 \(n\) 和 \(m (1 \le n,m\le 500)\) ，意义如上文所述。 接下来 \(n\) 行，每行 \(m\) 个字符 W 或 B 。意义如上文所述。 输出格式： 一行一个整数，表示把初始矩阵变...

CF1592F2 Alice and Recoloring 2 题解 题目链接：Alice and Recoloring 2 题意： 本题与 CF1592F1 的差异在于花费不同。 给定一个 \(n\) 行 \(m\) 列的目标矩阵，矩阵元素只有 W 或 B ，并且你有一个初始矩阵，元素全为 W 。 现在你可以矩阵实施以下操作： 使用一块钱，选定一个包含 \((1,1)\) 的子矩阵，把矩阵中的元素全部反转（ W 变 B ， B 变 W ）。 使用三块钱，选定一个包含 \((n,1)\) 的子矩阵，把矩阵中的元素全部反转。 使用四块钱，选定一个包含 \((1,m)\) 的子矩阵，把矩阵中的元素全部反转。 使用两块钱，选定一个包含 \((n,m)\) 的子矩阵，把矩阵中的元素全部反转。 现在需要你求出把初始矩阵变为目标矩阵最少需要几块钱。 输入格式： 第一行两个正整数 \(n\) 和 \(m (1 \le n,m\le 500)\) ，意义如上文所述。 接下来 \(n\) 行，每行 \(m\) 个字符 W 或 B 。意义如上文所述。 输出格式： 一行一个整数，表示把初始矩阵变...

CF1539F Strange Array 题解 题目链接：Strange Array 题意： \(\texttt{Vasya}\) 有一个长度为 \(n\) 的数组 \(a\)。 对于每一个元素 \(a_i\)，进行一次以下操作，可以获得的最大值称为 \(a_i\) 的奇异值： 选取一对 \(l,r\) 使得 \(1\le l\le i\le r\le n\)。 将区间 \([l,r]\) 中的元素从小到大排序，如果有相同元素，则可以任意排列它们的位置。 记 \(a_i\) 现在的位置为 \(x\)，定义序列中心 \(y\) 为 \(\lceil\frac{l+r}{2}\rceil\)，则距离为 \(|x-y|\)。 请你帮助 \(\texttt{Vasya}\) 求出每一个元素的奇异值，注意每个元素之间互不影响。 数据范围： \(1\le n\le 2\times 10^5,~1\le a_i\le n\) 。 好像是套路题，但我不知道。考虑区间已经确定且 \(a_i\) 升序排序后如何求距离 \(\rm dis\) 。 记 \(a_{\rm mid}\) 为中位数...

CF935F Fafa and Array 题解 题目链接：Fafa and Array 题意： 给出一个序列 \(a\)，定义函数 \(f(a)=\sum_{i=1}^{n-1}|a_i-a_{i+1}|\)。 给出两种操作: \(\texttt{1 l r x}\)，表示在区间 \([l,r]\) 内找一个位置， 使得把这个位置的值加上 \(x\) 后 \(f(a)\) 最大，求这个最大值（修改是临时的）。 \(\texttt{2 l r x}\)，表示把区间 \([l,r]\) 加上 \(x\)。 输入格式 第一行一个正整数 \(n~(3 \le n \le 10^5)\) ，表示数组的长度。 第二行 \(n\) 个正整数 \(a_{1},a_{2},...,a_{n}~(0 < a_i \le 10^9)\) ，表示数组的元素。 第三行一个正整数 \(q~(1 \le q \le 10^5)\) ，表示询问的个数。 接下来 \(q\) 行，第 \(i\) 行有四个整数 \(t_i,l_i,r_i,x_i~(t_i \in\{1, 2\},\,1<l_i ...

CF1685C Bring Balance 题解 题目链接：Bring Balance 题意： cxy 有一个长度为 \(2n\) 的括号序列 \(s\)，由 \(n\) 个左括号 ( 和 \(n\) 个右括号 ) 组成。她想把这个括号序列变成一个平衡括号序列。 平衡括号序列定义为：能通过插入字符 + 和 1 使之成为合法数学表达式的序列。例如，序列 (())()、() 和 (()(())) 是平衡的，而 )(、(() 和 (()))( 就不是的。 在一次操作中，她可以反转 \(s\) 的任意子串。 请求出最少几次操作可将 \(s\) 转换为平衡括号序列。可以证明，这总是能在 \(n\) 次操作中完成。 输入格式： 本题有多组数据。 第一行一个整数 \(t\)（\(1 \le t \le 2 \cdot 10^4\)），表示数据组数。 每组数据格式如下： 第一行一个整数 \(n\)（\(1 \le n \le 10^5\)），含义如上所述。 第二行为一个长度为 \(2n\) 的括号序列，由 \(n\) 个左括号 ( 和 \(n\) 个右括号 ) 组成。 在一个测试点中，所有...