P4221 [WC2018]州区划分我们考虑一个 $dp$ ，设 $dp[s]$ 表示 $s$ 这个集合城市得到的答案，$f[s]$ 表示 $s$ 集合城市的权值和（如果联通且存在欧拉路径我们视之为 0 ）。 于是有： dp[S] = \frac{1}{f[S]}\sum_{s\subset S} dp[s]f[S\setminus s]这东西形式看起来很像分治 FFT 啊（只是换成了 FWT 而已。。）。 我们考虑子集卷积最后推出的式子是： C_x' = IFMT(\sum_{0\le i ...

好巧妙的构造！ CF1034E Little C Loves 3 III一句话题意：求两个数组的子集卷积，模 4 ，$n \le 21$ 首先，我们显然会 $O(n^22^n)$ 的裸的子集卷积，在这里可以看到。但是显然不足以通过本题。 这里就要用上出题人的神仙构造了，令模数为 $p$ ，设 a'_i = a_i p^{popcount(i)}然后考虑将这样变换后的 $a,b$ 搞个或卷积，算出来是： [x](a' \times_{or} b') = \sum_{j|k = x} a_jb_ ...

CF1103D Professional layor你谷假翻译害人不浅 考虑先求出所有数字的 $\gcd$ ，这个数必然不超过 $10^{12}$ ，所以不同的质因数个数不超过 $11$ （拿前12个质因数乘起来就已经 $7 \times 10^{12}$ 了）。 然后考虑，我们肯定要把这 $\gcd$ 的质因数分解分成很多块质数，让某些数不再是某块质数的倍数。然后可以发现，如果可以做到必然有答案小于 12 。 于是就有了一个最简单的 dp 方案：$dp[i][j][s]$ 表示前 $i$ 个数 ...

P4169 [Violet]天使玩偶/SJY摆棋子首先这题显然可以 CDQ，分四个方向分别跑就行了，拆出来的条件是一个三维偏序问题。 但是 $3 \times 10^5$ 的数据范围导致 CDQ 很容易被卡常啊。。（实际上也确实有很多被卡了）。 所以考虑可以用玄学 K-DTree 来维护。 具体来说，考虑从根开始向下行走，每走一个点就更新一下答案。每次查一下这个点到两边矩形的最小距离是否超过了当前的答案，如果是就不走了。 一个优化是，每次先进入距离最小的子树。 这样最坏是 $O(n^2)$ 的， ...

P5631 最小 mex 生成树如果删掉某种权值的边，仍然可以连成一棵生成树，那么显然答案是小于等于这个数的。因为我们必然可以不要这种边权来构成一棵树，这样这棵树的 mex 必然不会大于这个数。 然后一种暴力的做法就来了：删除某种权值的所有边并且跑生成树，看是否联通。复杂度是 $O(wn\log n)$ 。 考虑优化，我们可以分治来做（类似不要某个物品的背包），$solve(l,r)$ 表示 $[l,r]$ 之间的权值删去时来做生成树。分治的时候就是加入 $[l,mid]$ ，然后 $solve ...

SP8791 Dynamic LCA用 LCT 可以实现动态的 LCA。。其实想想就知道这其实是一个非常简单的套路。 比如要求 $u , v$ 的 LCA ，先 access 一下 $u$ 然后在 access $v$ 的时候把最后一个虚实交替的位置给返回就好了。写出来大概长成这样： 123456int access( int u ) { for( int p = 0 ; ; p = u , u = fa[u] ) { splay( u ) , ch[u] ...

CF587F Duff is Mad这题如果往根号方面想还是比较容易想到做法的。另外这题可以不带 $\log$ 的！ 首先，区间内的串在某个串的出现次数，可以考虑广义 SAM 或者 ACAM。感觉两个东西都可以做这个题，为了复习 ACAM （为了去做上次 edu 的G）写下 ACAM 吧。 我们考虑 $s_{l\dots r}$ 在 $s_k$ 里出现次数这个问题。可以看成 对 $s_x,x\in [l,r]$ 看它在 $s_k$ 的出现次数。这个问题显然是可以前缀和的，也就是 $s_{1\do ...

P5047 Yuno loves sqrt technology II首先我们显然会一个非常辣鸡的 $O(n\sqrt m\log n)$ 做法而且看不出怎么优化。。 于是考虑上二次离线莫队。 设 $[a,b][c,d]$ 表示满足 $x\in [a,b],y\in [c,d],a_x>a_y$ 的数量，也就是两个区间之间的逆序对数。如果 $c<b$ 我们认为它没有定义。 我们考虑移动一个区间，比如从 $l,r$ 移动到 $l,r’$ ，增加量是： \sum_{i=r+1}^{r' ...

套路题 CF809E Surprise me!求： \frac{1}{n(n-1)}\sum_{i=1}^n\sum_{j=1}^n\varphi(a_i\times a_j)·dist(i,j)有一说一感觉这题非常套路。。模版练习题 然后看了看其他题解感觉 dp 部分可以不用做得那么麻烦吧（） 首先显然我们不管前面那个分数。然后发现式子里面有 $\varphi(a_i\times a_j)$ 这个不太好处理的东西。。思考一下，我们希望能够化成这样的形式： \sum_{i=1}^n \sum ...

3.25 模拟赛 A~BA String设 $n$ 为 $S_1$ 长度，$m$ 为 $S_2$ 长度。 我们考虑设 $f[i]$ 表示 $S_1$ 从 $i$ 开始向后 $m$ 个字母和第二个串相同的位置个数。我们把它写出来是： f[i] = \sum_{j=i}^{i+m} [S_1[j] = S_2[j - i]]稍微化简一下： f[i] = \sum_{p-q=i} [S_1[p]=S_2[q]]这一看就很像差卷积的形式！于是我们考虑对每个字符分开做，设 $s_1[i] = 1$ 表 ...

CF704D Captain America很套路的题吧。。唯一毒瘤的地方在于不是很有源汇上下界限最大流。。 考虑把坐标离散化一下，然后 $(x,y)$ 这个点就看成 $x \to y$ 连下界 0 上界 1 的边，表示这个点是选优秀的颜色还是不优秀的。 然后对于一个限制，我们考虑这上面有 $x$ 个点，其中两种点的差不能超过 $y$ ，这种时候这条直线上能够选择的优酷的点是在一个范围内的。推下式子可以得到，下界是 $\lceil \frac{x - y}{2} \rceil$ 上界是 $\lf ...

CF176E Archaeology学到了一个巨神的结论。。 虚树大小就是 dfs 序排序后相邻两个点的距离的和 + dfs序最左和最右两个点距离的和的一半 因为按照 dfs 序来走这些点，每个点向上的边都必然会在进入这个点的时候走一次，离开这个点的时候走一次。 所以导出子树这种东西一半都要往 dfs 序来想吧。。 然后这个东西的维护就变得简单了起来，开个 set 就做完了。 123456789101112131415161718192021222324252627282930313233343 ...

Dsu On Tree首先丢一下原文链接，写的很好：这里 是一种奇怪的科技。。在 cf 学了一下感觉看不出和 dsu 有多大的关系，貌似只是按秩合并的复杂度有点关。不过还是很妙的啦。。 我们考虑要做这样一件事：维护一个子树内的某种信息。比如我们要问某个点子树内的某种颜色的数量。我们显然可以拖到 dfs 序上跑主席树 于是本文终结，但是这里介绍另一种做法。。 我们考虑，一个最朴素的暴力到大一个点，清空 cnt 数组并且便历这个子树，到一个点就给这个点的颜色 + 1。这样做是稳定 $O(n^2)$ ...

FWT 整理以前我记得是正式写过 FWT 的总结的但是貌似没找到 作为一个背板选手详细证明被咕咕咕了，可以见 LSJ的blog) 注意几种卷积都满足可加性。 或卷积或的 FWT 是： FWT_{or}(A)[i] = \sum_{j\subseteq i} A[j]也就是 每个数的子集和。 或卷积满足 F W T(A)=\left\{\begin{array}{ll}\left(F W T\left(A_{0}\right), F W T\left(A_{0}\right)+F W T\le ...

CF 938 G Shortest Path Queries看到 XOR 最短路就可以想到 WC 最长XOR路径的做法，也就是把环都给丢进线性基里面，查询就查路径 XOR 值在 线性基能 XOR 出的最小值。 如果只有插入怎么做？插入的时候维护一下与 生成树 形成的环就好了。 可是现在不仅有了插入，还有删除。发现线性基这个东西不太好删除，于是可以按时间分治（线段树分治），维护每个边存在的时间段，最后 dfs 一次时间线段树解决问题。 但是既然有删除的存在，就必然存在图不联通的情况，而且删除也可能 ...

CF 990 G GCD Counting这种等于 $d$ 的题往往要化成一个比较好求的形式。。比如这个题，如果推 $=d$ 的式子最后发现点分时需要两次莫反，复杂度是 $O(n\log^3 n)$ ，但是一个比较好的思路就是求 $d$ 整除 $g(x,y)$ 的 $(x,y)$ 对数，如果设这样求出来的是 $s(x)$ ，并且我们最后要算的是 $f(x)$ 那么有： s(x) = \sum_{x|d} f(d)不难发现这是个狄利克雷前缀和的形式，可以卷回去，卷回去的复杂度仅仅是 $O(n\l ...

头文件都嵌博客里有点难看，专门开一个文章放头文件和 vimrc 之类的东西吧。 1234567891011121314151617181920212223242526272829303132333435#include "iostream"#include "algorithm"#include "cstring"#include "cstdio"#include "cmath"#include ...

终于写了一次 A ~ F 的全部题解。 CF1325 A ~ F CF Round 628一晚上补完了。。好累。。 以后代码头文件和宏定义太长的就不写上了，专门开个帖子放头文件吧。 A EhAb AnD gCd输出 $1 , n - 1$ 显然正确。 12345678910int n , k , P; void solve() { cin >> n; cout << 1 << ' ' << n - 1 &l ...

CF1240 A ~ D CF Round 591A Save the Nature为啥 A 放个这么长的题啊读着好累。。 二分一下在哪天之前结束，只需要判断当前最大捐款是否到达 $k$ 。这个贪心很显然， $(x+y)\%$ 的位置放最大的 $\frac{d}{\text{lcm}(a,b)}$ ，然后按照 $x,y$ 大小关系放剩下的最大的那部分就好了。 123456789101112131415161718192021222324252627282930313233343536373839 ...

CF1168 A~C CF Round 562A Increasing by Modulo这个我们操作 $k$ 次就是至多给一个数字 + k ，所以直接二分一下 $k$ 就好了。 12345678910111213141516171819202122232425262728293031323334353637383940414243#include<iostream>#include<cstdio>#include<cstdlib>#include<cs ...

CF1034C Region Separation好题啊 我们先考虑只进行一次操作，可以发现如果这次操作希望把整个树分成 $k$ 份，那么要么不可分，要么只有一种方案。 怎么证明？首先可以钦定 1 为根。如果希望把整个树分成 $k$ 份，那么每个联通块的大小必然是 $\frac S k$，其中 $S$ 是整个树的权值的和。然后很显然的，每个断开当前点和它父亲的边的必要条件是 $s_u \equiv 0 \pmod {\frac S k}$ 。但是，假设它的子树内已经有很多点被断开了，那么对于这个 ...

3.18 模拟赛 A拿到这题的第一个想法是能不能树形 dp ？然后发现不太好转移。 然后考虑 $k=n-1$ 的情况，这种情况显然我们选择了每一条小边，然后发现其实我们最后选择的方案必然是一些小边合并得到的。一次合并，其实就是在某个点我们拿两个断开的边接起来。 然后我们意识到这个过程的顺序是无关紧要的，于是我们可以把每个点单独看贡献。假设一个点度数是 $deg$ ，要选择 $p$ 对点来进行操作，于是 {deg\choose{2p}}\frac{(2p)!}{p!2^p}就是方案数量（这个式子 ...

ZROI 3.17 B我们考虑 恰好进行 $k$ 次这样的操作，就是让你求有多少个树，满足这个树和原来的树重复的边的数量不少于 $n - k - 1$。 考虑 $F[x]$ 表示重复边数量正好是 $x$ 的方案数量，然后这里用到了一个经典（但我不会）的套路，二项式反演（其实就是容斥），也就是说钦定一些边必须是相同的，剩下的边随意连形成的树， 考虑设 $f[x]$ 表示钦定 $x$ 条边必须相同，剩下的边任意连形成的树的个数，那么容斥一下就是： F[x] = f[x] - \sum_{i > x ...

SPOJ PERIODNI仍然考虑类笛卡尔树的 dp，我们把整个直方图画成了很多个矩形。首先考虑一个矩形内部的答案，如果这个矩形 $n$ 行 $m$ 列，并且我们要从中选择 $k$ 个点，方案数量就是，从行选择 $k$ 个，从列选择 $k$ 个，然后再任意组合。考虑任意组合的过程，就是从行的 $k$ 个点分别对应到一个列，也就是排列的数量，所以就是 $k!$ ，于是 $n\times m$ 的矩形选择 $k$ 个点的方案就是： S(n,m,k) = {n\choose k} {m\choose ...

神题！ LOJ 2743 JOI Open 2016 摩天大楼神仙题！ 我们考虑给数字排序一个一个加入排列。 考虑当前整个长度为 $n$ 的数列被加入了一些数字，形成了一些连续段。当我们即将加入 $A_i$ 时，我们钦定每个连续段的左右两端的仍然没有放下确定的差值为 $A_i-A_{L/R}$ ，然后当前放了一个数字在一个地方，如果它作为了某个段的左端 / 右端，那么这个差值就从 不确定的 变成了 确定的，并且除开这个左端（但是包含新加入的左端）的不确定的差值都会加上 $A_{i+1} - A_ ...

终于好好写了一次点分题！ 3.14 模拟赛 CTree考虑一个题目描述的三角形其实就是同色三角形的个数，是个经典问题，可以看成总方案数减去异色三角形数，于是问题变成了统计异色三角形的数量。我们知道一个异色三角形必然有两个边同色，我们考虑一个三角形 $u \to v , v\to t , u \to t$ （原题是有向的），那么我们在 $u\to v,u\to t$ 的位置统计下 $u$ ，再在 $v\to t,u\to t$ 的位置统计下 $t$ ，显然这两次统计一次统计同色一次统计异色，于是相 ...

CF1322C首先我们知道 $\gcd(a,a+b) = \gcd(a,b,a+b) = \gcd(a,b)$ ，这是显而易见的。 于是我们考虑对于两个右部点 $u,v$ ，假设与它们相邻的左部点集合是 $R(u),R(v)$ 这时它们的贡献。 $R(u) = R(v)$ 这种时候，只有在计算 $N(S),S\subseteq R(u)$ 的时候会计算到 $w_u+w_v$，其他时候它们均不做贡献。也就是说，我们可以合并这样的点，所有这样的点都会一起被计算。 $R(u) \subseteq R ...

AGC 026 D 一个很神仙的 dp，这题完全可以出到 $n \le 10^5$ 啊不知道为啥只有 100。。 考虑，第一行是黑白相间的，那么后面都必须黑白相间，有反色和复读两种情况。而如果第一行不是黑白相间的，那么下一行的构造就只能反色，所以一个第一行不是黑白相间的情况对应唯一一种方案。 然后我们可以按照套路类似笛卡尔树上的 dp，设 $dp[u][0/1]$ 表示当前在笛卡尔树的 $u$ 节点，这个节点所包含的区间是 黑白相间 / 任意排列 ，然后考虑怎么转移，设当前在节点 $u$ ，它下 ...

AGC 024 F我们考虑对于所有串 $S$ 计数它是多少个串的子序列。 我们假设 $(S,T)$ 为当前有一个字符串 $S$ ，我们要往后面加一些字符 $T’$ 并且是 $T$ 的一个子序列，转移类似子序列自动机来走，对于每个 $i$ 处理出 $nxt[i][c]$ 表示 $i$ 后面第一个 $c$ 的位置。 $T’ = \varnothing$ ，相当于走到了 $(S,\varnothing)$ 就是不再加字符了 $T’ = 0$ ，找到 $T$ 中第一个 0 ，跳过去，转移到 $(S+0 ...

A 至 C 略了。。没啥意思。。 Educational Codeforces Round 83 简要题解D Count the Arrays考虑我们从 $m$ 个数字中拿出 $n - 1$ 个数，其中一个需要放两遍，而且这个数显然不能是最大的（最大的放两遍就不满足 strict 了 ）所以乘上 $n - 2$，然后考虑对于除开放两遍、最大的数字的 $n - 3$ 个数字我们都需要决定它放在哪边，所以答案就是 (n-2)2^{n-3}{m \choose n-1}E Array Shrinki ...