最近被迫学习了一些多项式的知识，这篇文章算是把个人的理解写了下来吧，应该会有很多可以练习的题目。 完更内容包括：多项式基础，FFT 待填坑内容包括：NTT，FWT，多项式的高级运算，多项式的应用与技巧 多项式基础 多项式初中都学过，其实通俗点说，一个多项式 \(F\) 可以表示为 \(F(x)=a_0+a_1x+a_2x^2+...\)，其中称 \(x^i\) 为多项式的 \(i\) 次项， \(a_i\) 为 \(i\) 次项的系数。 一般来说，我们也常用 \(F[i]\) 来表示 \(a_i\)。 我们称一个多项式为 \(k\) 次多项式当且仅当该多项式系数不为 \(0\) 的...

\(\text{Solution}\) 我们设 \(dp_i\) 表示编号为 \(i\) 的节点到达该树叶子节点的最小花费，那么显然我们有以下的转移方程： \[dp_i=\begin{cases}0&i \text{ is leaf}\\\min\limits_{j \in child_s}\left\{dp_j+a_i \times b_j\right\}&\text{Otherwide}\\\end{cases} \] 直接转移是 \(\text{O}\left(n^2\right)\) 的，考虑如何优化。 我们令 \(dp_j+a_i \times b_j...

前言 上橙了，可喜可贺qwq。 A - String Generation 题目大意 构造一个长度为 \(n\) 且只有 \(a,b,c\) 三种字符的字符串，使得最长回文子串长度不超过 \(k\)。 解题思路 显然 \(abcabcabc...\) 构造的字符串最长回文子串一定是 \(1\)。 Code int t,n,k; signed main() { t=read(); while(t--) { n=read();k=read(); for(int i=1;i<=n;++i) printf("%c",i%3==1?'a':...

前言 第一次打进 rank100 的 div2，泪目 A - Cancel the Trains 题目大意 在一个 \(100 \times 100\) 的矩形中有若干列和若干行有一辆位于 左/下 且速度为 \(1\) 的车向 右/上 方向行驶，问最少去掉多少辆车才能不使任何两辆车相撞。 解题思路 简单观察就能发现两辆车会相撞当且仅当他们所在的行数与列数相等。 直接统计有多少个行列相同的车即可。 Code const int N=105; int t,n,m,vis[N]; signed main() { t=read(); while(t--) { n=rea...

Day -1 打了最后一场模拟赛，爆零了，感觉这次要没 Day 0 颓颓颓 Day 1 快进场的时候看了看 \(J\) 组的题，感觉T3没有一眼，rp--。 提前 10 分钟发的密码，结果第一次密码输错了，rp--。 开了题以后看到 t1 这个名字就感觉不妙，果然出了个大模拟，先大概看了一眼就去看后面几题了，然后发现 t2 是个大水题，t3 可以直接暴力拿几分，t4 好像可以模拟下，然后就回来肝 t1 了。 t1 一开始就想出来个二分年份的做法，感觉比较好实现，就写了，大概快一个小时的时候写完了。 测了一下第一个样例就没过，准备复制下来调试一下的时候，手残按了下 ctrl-z...

前言 手慢了，再给我10min就能 ak 了/dk C - Sequence Transformation 题目大意 给出一个数列，选择一个数使得这个数将这个数列划分成的段数最小。 解题思路 直接记录一个数上一次的出现位置，如果上个位置 \(x\) 与当前位置 \(y\) 的距离 \(y-x>1\) ，那么这个数划分成的段数就加一。 Code const int N=2e5+5; int t,n,vis[N],sum[N],ok[N]; signed main() { t=read(); while(t--) { n=read(); for(int i=...

A - Subtract or Divide 题目大意 给你一个数 \(n\) ，每次可以将这个数除去一个他的因子（不能是他本身）或减一，问把这个数变成 \(1\) 的最少操作数量。 解题思路 这题比较降智，其实有一个很简单的贪心思路。 如果 \(n\) 是偶数，那么就可以直接一次把这个数除成 \(2\)，再减一，共 \(2\) 次操作。 如果 \(n\) 是奇数，那么可以先减一变成偶数，再仿照偶数的操作，共 \(3\) 次操作。 显然这样一定会使操作次数最少，不过要特判下 \(1,2,3\) 的情况。 Code int t,n; signed main() { t=re...

<button class="accordion">吐槽 分类讨论 + 构造大赛（雾 B分类讨论的时候不小心把 0 打成 1 FST，D初值设小不然 1h 就过了，直接把上分场整成了掉分场，枯了。 </button> A - XORwice 题目大意 给你 \(a\) 和 \(b\)，求 \((a \oplus x) + (b \oplus x)\) 的最小值。 解题思路 考虑怎么构造 \(x\) 才能使要求的值最小。 对于每一位，如果 \(a,b\) 都是 \(0\) ，那么当 \(x\) 的这...

什么是线性基 线性基大概可以理解为对于一组数 \(A_1,A_2...A_n\) ，构造出一个大小为 \(\text{O}\left(\log_2\text{N}\right)\) 的一个数组 \(P\)（\(\text{N}\) 即为数组 \(A\) 中数的值域），使得数组 \(A\) 中的任意数都可以由数组 \(P\) 中的数异或得出。 在满足此条件时，线性基的大小应该尽可能的小。 线性基的性质 数组能通过数组 \(A\) 中的数异或得出的数同样能够通过数组 \(P\) 中的数异或得出。 线性基能表示出数组的所有数，所以一定可以表示出数组中数的异或值 ...

前言 \(\;\) 个人纯属菜鸡，进省选是靠的奖励名额，所以这篇游记可能是我个人的受虐记（（ \(\;\) $$ \text{Day-0} $$ \(\;\) 下午还在地生模拟，晚上就到济南省选（（ \(\;\) 到的时候已经 9 点了，没来得及试机（ \(\;\) 菜的只会线段树，想着模板那么多也就索性颓废了。 \(\;\) $$ \text{Day-1} $$ 出宾馆前简单温习了下逆元和组合数。 \(\;\) SD 省选竟然用 Windows ，考前我还害怕不会用 Linux 的编译器。 \(\;\) 提前半个小时进机房，电脑不错，就是 Dev 不能调试。...

题目翻译 给出 \(R\) 对红色木棍 \(r_1,r_2...r_R\)，\(G\) 对绿色木棍 \(g_1,g_2...g_G\)，\(B\) 对蓝色木棍 \(b_1,b_2...b_B\) 的长度（ \(R,G,B \le 200\) ），每次可以选出两对颜色不同的木棍组成一个矩形，每对木棍只能使用一次，木棍可以有剩余。请最大化所有组成的矩形的面积。 思路 很容易想到一个贪心的思路即在同一种颜色的木棍中，如果一对长度为 \(k\) 的木棍选过，那么所有长度大于 \(k\) 的木棍都已经选过。 那么可以先将每种颜色的木棍排降序，这样最优解所选的木棍一定是这个颜色的一个前缀。 这样...

题目翻译 有一个 \(n \times m\) 的 \(01\) 矩阵，可以修改一些位置，使得矩阵中的所有 长度为偶数的正方形子矩阵里的 \(1\) 的数量为奇数。求出最少的修改次数。 如果无论怎么修改都无法完成，输出 \(-1\)。 思路 显然一个 \(4 \times 4\) 的子矩阵可以由 \(4\) 个 \(2 \times 2\) 的矩阵构成。 但是如果这 \(4\) 个 \(2 \times 2\) 的矩阵中 \(1\) 的数量都是奇数，那么 \(4 \times 4\) 大小的矩阵里 \(1\) 的数量就是：奇 \(+\) 奇 \(+\) 奇 \(+\) 奇 \(=\)...

翻译 给你一个长度为 \(n\) ( \(n \le2 \times 10^5\) ) 的只包含数字字符的串 \(t\) ，请你删除一些的字符，使得将第一个字符移动到末尾得到的串和将最后一个字符移动到开头得到的串相等。 求出最少要删除多少个字符。 思路 先观察满足上述条件的字符串有什么特点，分类讨论下： 当一个串的长度为偶数时： 假设我们有一个长度为 \(6\) 的字符串 \(A\) ： 那么将第一个字符移动到末尾得到的串和将最后一个字符移动到开头得到的串以及他们的相等关系就是： 那么把这些相等关系整理出来就是： \(A_6=A_2=A_4=A_6\) \(A_1=A_3...

题目翻译 刚开始给你一个空的数组 \(b\ (b_i \le 10^6)\) , 每次可以将任意一个数填入该数组中 , 但是必须保证第 \(i\) 次放完后该数组的 \(\text{mex}\) 为 \(a_i \ (a_i\le 10^5)\)。请你求出放数字的顺序。若没有合法的顺序就输出 -1 。 数据保证 \(a\) 数组单调上升。 一个数组的 \(mex\) 即在这个数组中最小的没有出现过的自然数。 思路 CF 的传统构造题 , 其实很好想。 显然，如果 \(a_i>=i\) 那显然是没有合法的顺序的，因为如果要使第 \(i\) 次的 \(\text{mex}=a_i...