immix's blog

A - Snack 题意 有 ddd 天，每天可以选择花费 1/3/4/61/3/4/61/3/4/6 元购买四种不同的零食，求 ddd 天总共恰好花费 nnn 元的购买方案数。 两个购买方案不同当且仅当存在一天购买的零食不同. d≤2×105,n≤106d\le 2\times 10^5, n\le 10^6d≤2×105,n≤106。 解法 定义： 普通生成函数（OGF）：一个序列 ⟨an⟩\left\langle a_n\right\rangle⟨an​⟩ 的 OGF 是一个形式幂级数（可以看作无限长的多项式）A(x)=∑i=0∞aixiA(x) = \sum_{i=0}^{\infty} a_i x^iA(x)=∑i=0∞​ai​xi，其中 aia_iai​ 是数列的第 iii 项。 通过类比一般多项式的乘法，可以得到 OGF 的加法和乘法。 设 a,ba,ba,b 的 OGF 分别是 F(x),G(x)F(x), G(x)F(x),G(x)，则： OGF 的加法：F(x)+G(x)F(x) + G(x)F(x)+G(x) 对应的数列是 ⟨an+bn⟩\left\langle ...

邻项交换法 问题背景：给定 nnn 个元素 a1,a2,…,ana_1,a_2,\ldots,a_na1​,a2​,…,an​，要求求出一个最优的排列顺序 ppp，使得 f(ap1,ap2,…,apn)f(a_{p_1},a_{p_2},\ldots,a_{p_n})f(ap1​​,ap2​​,…,apn​​) 最优。 定义一种二元关系 ⪯\preceq⪯：x⪯yx\preceq yx⪯y   ⟺  \iff⟺ 对于任意的元素前缀和后缀，f(…,x,y,…)f(\ldots, x,y, \ldots)f(…,x,y,…) 都不比 f(…y,x…)f(\ldots y,x \ldots)f(…y,x…) 劣。 若这种关系是一种全预序（满足自反性，传递性，连接性）： 自反性：x⪯xx\preceq xx⪯x，根据定义显然永远成立。 传递性：∀a,b,c\forall a, b, c∀a,b,c，若 a⪯ba \preceq ba⪯b 且 b⪯cb \preceq cb⪯c，则 a⪯ca \preceq ca⪯c，需要根据序关系具体验证。 连接性：∀a,b\forall a, b∀a,b， ...

最小（不重）路径覆盖 给定一个 DAG，求把 DAG 划分为若干条路径，使得每个点都恰好某个路径上的方案中，路径条数最小是多少。 考虑初始化为 nnn 条路径，每个路径就是一个单点。然后如果有一条边 (u,v)(u,v)(u,v)，就可以合并一条以 uuu 为结尾的路径和以 vvv 为开头的路径。最后答案就是 n−合并次数n-\text{合并次数}n−合并次数。 考虑如何刻画这样的合并过程，我们发现，每个点作为开头和作为结尾都至多被合并一次，那么我们就把每个点拆成两个，(u,u′)(u,u')(u,u′)，uuu 和 sss 连接，u′u'u′ 和 ttt 连接，用边 (u,v)(u,v)(u,v) 连接就对应了一条增广路 s−u−v′−ts - u - v' - ts−u−v′−t，这样正好表示了 uuu 作为结尾被合并了一次，vvv 作为开头被合并了一次，所以所有边权设置为 111 就能刻画出每个点最多被合并一次的限制。 至于输出方案，也是简单的，一个点是链的开头，就说明它没有作为开头被合并过，也就是它的第二个点到 ttt 的边没有流量，判断之后 df ...

AC 自动机 定义与构建 AC 自动机是解决多模式匹配的一类自动机。 假设现在有若干个字符串 s1,s2,…,sks_1,s_2,\ldots,s_ks1​,s2​,…,sk​，构建出它们的 Trie。AC 自动机关键在于求出 fail 指针，定义为最长的在 Trie 中出现过的公共前后缀。 代码如下： 1234567891011121314151617181920212223242526272829// 记得修改字符集大小和字符种类const int SIGMA = 26;const char BASE = 'a';int ch[N][SIGMA],fail[N],cnt[N],tot=1;void ins(const string& s){ int u=1; for(int i=0;i<s.size();i++){ int c=s[i]-BASE; if(!ch[u][c])ch[u][c]=++tot; u=ch[u][c]; } cnt[u]++;& ...

分治 NTT 给定序列 g1…n−1g_{1\dots n - 1}g1…n−1​，求序列 f0…n−1f_{0\dots n - 1}f0…n−1​。 其中 fi=∑j=1ifi−jgjf_i=\sum_{j=1}^if_{i-j}g_jfi​=∑j=1i​fi−j​gj​，边界为 f0=1f_0=1f0​=1。 答案对 998244353998244353998244353 取模。 考虑对原序列进行分治，假设当前要求出的区间是 [l,r][l,r][l,r]，其中 [l,mid][l,mid][l,mid] 已经递归左半部分算完，那么我们需要先考虑 [l,mid][l,mid][l,mid] 对 [mid+1,r][mid+1,r][mid+1,r] 的贡献再递归右半部分即可。 那我们发现，[l,mid][l,mid][l,mid] 对于 [mid+1,r][mid+1,r][mid+1,r] 的贡献是一个卷积形式。所以我们把 f[l,mid]f[l,mid]f[l,mid] 和 g[1,r−l]g[1,r-l]g[1,r−l] 抽出来做一个 NTT 卷积，然后把答案加到右边，之后 ...

Min 25 筛 Min 25 筛是用来求出积性函数前缀和的方法。 如果你不知道什么是积性函数： 积性函数：∀a⊥b:f(ab)=f(a)f(b)\forall a\perp b:f(ab)=f(a)f(b)∀a⊥b:f(ab)=f(a)f(b)； 完全积性函数：∀a,b:f(ab)=f(a)f(b)\forall a,b:f(ab)=f(a)f(b)∀a,b:f(ab)=f(a)f(b)。 本文中，若无特殊说明，ppp 表示质数。 第一步 - 求出函数质数部分的前缀和 做法 此步我们要求 fff 是完全积性函数，在题目中 f(p)f(p)f(p) 往往是关于 ppp 的多项式，这样就可以拆成若干个完全积性函数，也就是说，我们期望 f(p)f(p)f(p) 的表达式较简单。 即求 g(n)=∑p≤nf(p)g(n) = \sum_{p\le n} f(p)g(n)=∑p≤n​f(p)。 设 pjp_jpj​ 为第 jjj 个素数（即p1=2p_1=2p1​=2），特别地，令 p0=1p_0=1p0​=1。 设 g(n,j)g(n, j)g(n,j) = ∑i=1n[i是质数∨i 的 ...

容斥原理 对于集合 S1,S2,…,SnS_1, S_2, \ldots, S_nS1​,S2​,…,Sn​: ∣⋃i=1nSi∣=∑i∣Si∣−∑i<j∣Si∩Sj∣+∑i<j<k∣Si∩Sj∩Sk∣+⋯+(−1)n−1∣S1∩⋯∩Sn∣\begin{aligned} \left|\bigcup_{i=1}^{n}S_i\right|=&\sum_{i}|S_i|-\sum_{i<j}|S_i\cap S_j|+\sum_{i<j<k}|S_i\cap S_j\cap S_k|+\cdots+(-1)^{n-1}|S_1\cap\cdots\cap S_n| \end{aligned} ​i=1⋃n​Si​​=​i∑​∣Si​∣−i<j∑​∣Si​∩Sj​∣+i<j<k∑​∣Si​∩Sj​∩Sk​∣+⋯+(−1)n−1∣S1​∩⋯∩Sn​∣​ 也就是说，对于满足若干个性质中至少一个的元素，可以用同时满足若干个性质的元素个数进行容斥（满足一个的 - 满足两个的 + 满足三个的……） 如果对于上式稍加修改，我们也能得出集合交集 ...

最近公共祖先 最近公共祖先（LCA）指的是两个或多个点的公共祖先中离根最远的一个。 对于 LCA 问题，有多种算法可以求解。 倍增 过程 先将树进行一遍 DFS，预处理出 fau,i\textit{fa}_{u,i}fau,i​ 表示节点 uuu 的 2i2^i2i 级祖先。 接下来对于两个节点 u,vu,vu,v，先根据两个节点的深度之差 ∣depu−depv∣|\textit{dep}_u - \textit{dep}_v|∣depu​−depv​∣，将较深的节点用 fa\textit{fa}fa 数组，通过 O(log⁡n)O(\log n)O(logn) 次操作跳到一样深。 当两个节点一样深之后，若此时两个节点相同，直接返回。 否则需要找到最小的 ddd，使得 uuu 和 vvv 的 ddd 级祖先相同。为次，我们从最大的 iii 开始，依次递减到 000，每次如果 fau,i≠fav,i\textit{fa}_{u,i}\ne \textit{fa}_{v,i}fau,i​=fav,i​，就将 u←fau,i,v←fav,iu\gets \textit{fa}_{u,i}, ...

数位 DP 数位 DP 是一种快速求解出在 [1,n][1,n][1,n] 满足条件的数个数的方法。其特点有数据范围一般均为 101810^{18}1018 次方量级（甚至更高）。 对于这种问题，我们是有一套通用的记忆化搜索模板的。 记忆化搜索 数位 DP 有不使用记忆化搜索的递推写法，但是记忆化搜索写法具有好实现的优点，而且一般记忆化搜索是可以做所有数位 DP 的题目的。 我们从一道题目出发来讲解通用的记忆化搜索方法。 示例题目 LOJ#10164. 「一本通 5.3 例 2」数字游戏 给定两个正整数 aaa 和 bbb，求在 [a,b][a,b][a,b] 中的所有整数中，有多少个数满足从左到右各位数字成小于等于的关系。 1≤a≤b≤231−11\le a\le b\le 2^{31}-11≤a≤b≤231−1。 解法 首先我们需要知道，对于区间 [a,b][a,b][a,b] 来说，可以拆分成求 [1,b][1,b][1,b] 和 [1,a−1][1,a-1][1,a−1] 的答案，然后将结果相减，因此后面我们只需考虑求出 [1,n][1,n][1,n] 的所有整数中各数码出现个 ...

生成树 定义连通无向连通图 GGG 的生成树是有 GGG 的一个树子图。 最小生成树 相关概念与性质 定义带权无向图的最小生成树是其各边边权和最小的生成树。 定义带权无向图的瓶颈生成树该图生成树中，最大的边权最小的生成树。 最小生成树一定是瓶颈生成树，瓶颈生成树不一定是最小生成树。 边权各不相同的图最小生成树唯一。 一张图所有最小生成树同一权值边数量相同。 一张图上两点之间所有路径最大边的最小值 = 最小生成树上两点路径最大边。 算法 一般有三种算法可以用来求最小生成树，实际做题时应根据题目灵活选用适合的算法。 Kruskal 将边从小到大排序，依次遍历，如果当前边的两个端点之间没有连通就加入这条边，最后加入的边构成的就是最小生成树。 用并查集维护连通性。 复杂度 O(mlog⁡m)O(m\log m)O(mlogm)。 模板代码： 12345678910111213141516171819202122232425262728293031323334353637#include<bits/stdc++.h>using namespace std;const int N ...