Meteorshower_Y

# 反演 # 二项式反演 如果有 : f(x)=∑i=0n(−1)i∗(ni)∗g(i) f(x) = \sum _{i = 0} ^{n} (-1) ^{i} * \binom{n}{i} * g(i) f(x)=∑i=0n​(−1)i∗(in​)∗g(i) 那么有 : g(x)=∑i=0n(−1)i∗(ni)∗f(i) g(x) = \sum _{i = 0} ^{n} (-1) ^{i} * \binom{n}{i} * f(i) g(x)=∑i=0n​(−1)i∗(in​)∗f(i) #...

# 多项式学习笔记 做多项式题就像嗑药，出多项式题就像贩毒。—— 某 FJOI 某知名选手 # 快速傅里叶变换（Fast Fourier Transform） 快速傅里叶变换，指利用计算机快速高效的计算离散傅里叶变换的方法，简称FFT。 # 离散傅里叶变换（Discrete Fourier Transform) 这是一种将多项式的系数表示法变为点值表示法的一种方法，简称 DFT，时间复杂度为优秀的 O(nlog⁡n)O(n \log n)O(nlogn)。 我们有下面的多项式： A(x)=a0+a1x+a2x2+a3x3+...+anxnA(x) = a_0 + a_1 x + a_2...

# 后缀自动机 (Suffix automata, SAM) 参考资料 : KesdiaelKen 的博客 OI-WiKi 后缀自动机 (SAM) 此篇博客中的大部分图转自 KesdiaelKen 的博客，如有侵权，请联系删除 (此篇博客的示例字符串为 aababa ) ( fafafa 边在其他博客或许被称作 后缀 link（后缀链接）) # 概述 后缀自动机 (Suffix Sutomaton, SAM) 是一个能解决许多字符串相关问题的有力的数据结构 . 一个字符串的 SAM 是一个接受原字符串的所有后缀的最小 DFA (确定性有限自动机或确定性有限状态自动机) . SAM...

# Cats Transport # 题目大意 有 mmm 只小猫要在 nnn 个山丘上玩耍，雇佣了 ppp 个人接它们回来，这些人均在 111 号山丘出发。山丘 iii 与山丘 i−1i-1i−1 的距离是 DiD_iDi​ 米，每时刻人们走 111 米。 小猫 iii 会在山丘 HiH_iHi​ 玩耍，并在时间 TiT_iTi​ 结束它的游玩，然后在山丘上等着有人来接它。一个人在路过这个山丘时会把在等待的小猫带上（不需要额外的时间）。 我们需要安排每个人的出发时间，使小猫们的等待时间之和最小，输出这个最少的等待时间。 # 解题思路 计算出各只小猫被接到的出发时间...

# 岛屿观测 # 题目描述 一个长度为 nnn 的数列 aia_iai​ 和 长度为 nnn 的河床，第 iii 个数表示 位置 iii 的河床高度，对于一个高度 hhh，河床高度小于 hhh 的地方被淹没，大于等于 hhh 的连通块个数为岛屿数量。 操作一： 将位置为 pospospos 的河床高度修改为 hhh。 询问二： 询问河水高度为 hhh 时的岛屿数量。 # 解题思路 查询的意义是找到高度大于等于 hhh, 两边的最小值比 hhh 要小的点的数量，我们可以用两棵权值树状数组维护点数和，修改的时候先减去原来的值，再加上要修改的值即可。 还需要注意的一点是， a0a_0a0​ 要赋值为...

# Sasha and a Very Easy Test # 解题思路 因为模数 PPP 不一定是质数，不一定存在逆元，所以除法的操作需要特殊处理。 考虑一个数只有与模数 PPP 不互质时才没有逆元，我们可以考虑将 PPP 质因数分解，那么一个数被分成两部分：与 PPP 互质的部分 和 与 PPP 不互质的部分。与 PPP 互质的部分是 PPP 中不包含的质因数 (的乘积)，不互质是包含的部分。 互质的部分除就直接乘逆元，不互质的部分需要记录一个数所含 PPP...

# Trees # 题目描述 在长度为 nnn 的序列里选出 kkk 个数，这些数的贡献为最大的数的数值。为可选择的所有方案的权值和。 # 解题思路 不方便去快速求出子序列的最大值，我们可以枚举这个最大值，然后乘上选剩下 k−1k-1k−1 个数的方案数就能求出一个最大值的贡献了。把所有数作为最大值的贡献加起来就是答案。至于选数的的方案数，组合数学求下就好。 #include<algorithm>#include<iostream>#include<cstdio>using namespace std;#define long...

# One to one # 题意描述 给定一个数组 XiX_iXi​ ，F (X) 值的定义为，在一个第 iii 条边为 (i,Xi)(i, X_i)(i,Xi​) 的无向连通图的连通块个数。 现有一个序列 aia_iai​ ，一些位置为 −1-1−1 ， 则这个位置可以为 111 ~ nnn 中的任意一个数，问所有可能的 aaa 的 F(a)F(a)F(a) 之和对 998244353998244353998244353 取模的值。 n≤2000n \le 2000n≤2000 # 解题思路 对于给出的边，可以构成若干个 树和环...

\Huge{Hello \; World}\\\ \Large{This \; is \; Aniciry's \; blog.}\\ \Large{Welcome \; for \; everyone.}\\

# CF1192B 题解 题目链接 跟着 duyidalao 的思路，轻而易举 (qian nan wan xian) 调出了本题。 既然 @ duyi 没放代码，那我就来一发吧。 # 题意简述 有一个 nnn 个点的带权无向树， qqq 次操作，每次修改一条边的权值，要求在每次修改后，输出树的直径大小，强制在线。 # 题目分析 对于两棵树合并后新树的直径，其两端点一定出自两树直径四个端点中，根据这一条性质我们就可以用线段树维护原树，自下向上合并节点就相当于合并它所代表的两棵子树。 每次合并的时候，需要我们计算树上两点间距离，记该节点到根的距离为...