Thy's Blog

Day -1 整天呆在机房，上午打了 nfls 最后一场省选模拟赛，三道题全都挂分了，下午补了题顺便看了眼 HBOI 出的模拟赛，T1 想到了一个 O(nnlog⁡n)\mathcal{O}(n \sqrt n \log n)O(nn​logn) 的乱搞做法但是 TLE 成了 909090 分，加了一个根号分治的记忆化极限卡过了。 Day 0 上午 111111 点整起来的，但还是很困，吃完饭就赶去火车站了，中途还把身份证落在出租车上了……到达上饶已经快六点了，吃完回到家就顺便看了一下自己的笔记，顺便刷了刷 LA 群，虽然这次比赛已经无所谓了但还是很紧张，大晚上的睡不着觉，差不多凌晨两点才完全入睡。 Day 1 睡了 5.55.55.5 个小时，起来有些神志不清了，去餐厅随便吃了点早饭（感觉完全没有怎么吃），徒步前往考场。到考场已经 8:108:108:10 左右了，随手发了条朋友圈，然后排队进入考场，当时到了一堆人啊。查完身份后坐到机位上，是非常舒服的看片位角落，而且我右边的人缺考了，非常好。 打开编辑器的那一瞬间就感觉不对劲，没错，这键盘延迟高的离谱，感觉不会打字了，把显示器刷新率 ...

树形背包好题，推式子感觉十分自然，刚好用 LaTeX\LaTeXLATE​X 推的式子顺便写一下题解。 Statement 给定一颗 nnn 个节点的无向树，要求选取 kkk 个特殊点，与这些特殊点相连的点（除自身外）被覆盖，求把 nnn 个点全部覆盖的总方案数，答案对 109+710^9 + 7109+7 取模（1≤n≤105,1≤k≤min⁡(n,100)1 \le n \le 10^5, 1 \le k \le \min(n, 100)1≤n≤105,1≤k≤min(n,100)）。 Solution 根据题意和数据范围不难想到是一个 O(nk)\mathcal{O}(nk)O(nk) 的树形背包，因此我们直接上二维状态 dpver,kdp_{ver, k}dpver,k​ 表示以 ververver 为根的子树中选取 kkk 个特殊点并且合法的总方案个数。 发现转移很难，因为不能表示所有的状态，父亲节点选取与否会影响它的子节点，考虑增加一维，定义 dpver,k,0/1dp_{ver, k, 0 / 1}dpver,k,0/1​ 表示以 ververver 为根的子树中选取 k ...

题目链接：Problem - 1823F - Codeforces Statement 给定一棵 nnn 个节点的树，求从节点 SSS 到 TTT 过程中经过每个点次数的期望值，答案对 998244353998244353998244353 取值，n≤106n \le 10^6n≤106​。 Solution 定义 fif_ifi​ 表示经过点 iii 的期望次数，根据随机游走的套路，我们可以得出如下关系： fi={∑(i,j)∈E,j≠Tfjdeg⁡j+[i=S],i≠T1,i=Tf_i = \begin{cases} \sum\limits_{\substack{(i, j) \in E, j \neq T}} \frac{f_j}{\deg_j} + [i = S] , & i \neq T \\[10pt] 1, & i = T \end{cases} fi​=⎩⎨⎧​(i,j)∈E,j=T​∑​degj​fj​​+[i=S],1,​i=Ti=T​ 很好解释的状态转移，一旦走到 TTT 就结束，因此 fT=1f_T = 1fT​=1，剩余的过程中由于 SS ...

在掌握了多项式的加法和乘法，并且通过 FFT 和 NTT 将时间复杂度降到了可以接受的 O(nlog⁡n)\mathcal{O}(n \log n)O(nlogn)，我们就可以完成许多代数可以完成的基本运算了。 多项式乘法 P3803 【模板】多项式乘法（FFT） - 洛谷 前面已经详细讲过了，也是最基础的，这里放下完整代码。 FFT 记录详情 - 洛谷 | 计算机科学教育新生态 123456789101112131415161718192021222324252627282930313233343536373839404142struct Complex{ double a, b; Complex(double _a = 0, double _b = 0) : a(_a), b(_b) {} Complex operator + (const Complex &rhs) const { return Complex(a + rhs.a, b + rhs.b); } Complex operato ...

原本应该放在同与代数里面讲的，但是我还没有系统地学过，因此单独说一下。 前置知识 前置知识不多，只要涉及费马小定理和欧拉函数。 欧拉函数 欧拉函数 φ(n)\varphi(n)φ(n) 表示小于等于 nnn 的与 nnn 互质的数的个数。特别的，素数的欧拉函数 φ(p)=p−1\varphi(p) = p - 1φ(p)=p−1。 欧拉函数有如下性质： 是积性函数，∀gcd⁡(a,b)=1\forall \gcd(a, b) = 1∀gcd(a,b)=1，都有 φ(a,b)=φ(a)φ(b)\varphi(a, b) = \varphi(a) \varphi(b)φ(a,b)=φ(a)φ(b) n=∑d∣nφ(d)n = \sum_{d \mid n} \varphi(d)n=∑d∣n​φ(d)​ 如果 gcd⁡(a,m)=1\gcd(a, m) = 1gcd(a,m)=1，则有 aφ(m)≡1(modm)^{\varphi(m)} \equiv 1 \pmod mφ(m)≡1(modm) 由容斥原理可知，φ(n)\varphi(n)φ(n) 可以由公式： n=∏i ...

前言 这一节用于讲解拉格朗日插值法（Lagrange Polynomial）和快速傅里叶变换（Fast Fourier Transform），但是含有前置知识，因此有大量学过的知识可以直接跳过，存在大量证明会放出相应的链接。 多项式 基本概念 我们将形如 ∑anxn\textstyle{\sum a_nx^n}∑an​xn 的有限项相加式子成为多项式，记作 f(x)=∑i=0naixif(x) = \textstyle{\sum_{i = 0}^n a_i x^i}f(x)=∑i=0n​ai​xi。 如果是形如 ∑i=0∞aixi\textstyle{\sum_{i = 0}^\infty a_i x^i}∑i=0∞​ai​xi 的无限项相加式，则称为形式幂级数，后面应该会讲到。 aia_iai​ 被称为第 iii 次项的系数，记作 [xi]f(x):=ai[x ^ i]f(x) := a_i[xi]f(x):=ai​，对于 ∀ai(i>n)\forall a_i(i \gt n)∀ai​(i>n)，均为 000。 多项式的系数非零的最高次项的次数为该多项式的度，也 ...

zkw 线段树 zkw 线段树，即非递归版本的线段树，本质上与普通线段树一样，但是在一些较为简单或者有特殊性质的操作上（例如单点 / 区间修改，查询区间和 / 最值）有着码量小，空间少，常数小等特点（但是常数仍然略大于 Fenwick Tree）。 算法流程 在先前的普通线段树上，我们的每一次操作都是从线段树的根节点开始向下递归的，这种写法直观并且扩展性强，而 zkw 线段树则是从叶子节点一步一步上跳的，最终回到根部节点，有效的规避了递归模块的同时维护了区间信息。 建树 因为遵循着从底向上的原则，我们要算出线段树的叶子节点的标号是从哪一个开始，如图： 这颗线段树的叶子节点编号为 [8,15][8, 15][8,15]，不难发现 8=2⌈log⁡2n+1⌉−18 = 2 ^ {\left \lceil \log_2{n + 1} \right \rceil - 1}8=2⌈log2​n+1⌉−1，其中 nnn 为数组大小，并且 15−8=n15 - 8 = n15−8=n，因此我们得知了线段树上叶子节点的所有下标：令 T←2⌈log⁡2n+1⌉−1T \gets 2 ^ {\left ...

AC 自动机 前缀函数以及 KMP 算法很好的处理了单个模式串和文本串之间的字符匹配问题，但是如果存在多个模式串对于单个文本串进行匹配时，每个模式串都要和文本串进行一次预处理，时间复杂度为 O(n(∣T∣+∣S∣))O(n (|T| + |S|))O(n(∣T∣+∣S∣))，nnn 为模式串个数，∣T∣,∣S∣|T|,|S|∣T∣,∣S∣ 为模式串和文本串长度。 而 AC 自动机很好的解决了这个问题，AC 自动机（Aho-Corasick Automaton）是一种同样利用了 KMP 思想，以 Tire 树为结构的多模式匹配算法。 算法过程 AC 自动机的过程分为两步：建立 Trie 树以及预处理失配指针。 建立 Trie 树 不多赘述，Trie 树上的每一个节点表示某一个模式串的前缀。 12345678910inline void insert(char *str){ int cur = 0, len = strlen(str); for (int i = 0; i < len; i ++) { int k = str[i] ...

AC Library [AC Library](atcoder/ac-library: AtCoder Library) 是 AtCoder 官方推出的已经完全封装的缺省源代码，为了减少参赛者在像线段树、平衡树等数据结构或者取模方面浪费过多的时间，允行直接进行调用。 首先先前往 Releases · atcoder/ac-library 下载最新版的文件。解压后里面的 atcoder 文件夹即为整个库，复制后直接丢进本地编译器的库文件中，差不多类似 mingw64/lib/gcc/.../include/c++ 的文件夹中。 使用方法 头文件引用：#include <atcoder/all> 名称标签声明：using namespace atcoder modint 位于 <atcoder/modint> 当中，使用时需要先选择一个模数。 如果模数  mod \bmodmod 为 998244353998244353998244353 或 100000000710000000071000000007​，那么有现成的类可用，使用定义：typedef atcder: ...

好久没有写题解了，刷到了一道非常组合的题目。 Statement 给定整数 NNN （N≤500N \le 500N≤500）和不固定模数 MMM，求出 NNN 个点连出无向图的个数，满足顶点 111 到 NNN 的最短距离严格大于顶点 111 到其他节点的最短距离。 Solution 模数不一定为质数，因此在得到模数之后再预处理组合数组。 首先固定节点 111 和节点 NNN，NNN 毫无疑问是唯一距离 111 最远的一个点，因此考虑 distdistdist 从小到大进行转移。注意力惊人的话注意到边权为 111，因此可以将整幅图进行分层，然后就可以定义出 dpi,jdp_{i, j}dpi,j​ 表示固定了前 iii 个点，最后一层有 jjj 个点的方案总数。 显然每一个点只会在一层出现，答案即为 distN,1dist_{N, 1}distN,1​。 考虑如何转移，首先遍历二维数组肯定是 N2N^2N2 级别的。时间复杂度允许我们多一个 NNN 用来枚举上一层有几个点，即 dpi,j←dpi−j,kdp_{i, j} \gets dp_{i - j, k}dpi,j​←dpi−j ...