退役前的做题记录

2023.1.25

loj502

经典的倍数随机题。

这种什么某种颜色的出现次数是的倍数的题，一律都是对颜色赋予一个随机权值，然后用权值和是否是的倍数来做判断。做一个下比较大的维度向量的正确性是极高的，这题取即可。至于哪种颜色出现一遍，我们只用判断某种颜色的一倍或者两倍是否是当前权值即可。时限不太松，所以要对其压位，我这里压了位，预处理以内的加法即可。时间复杂度，这样复杂度比较松，用 umap 都可以通过。

2023.1.26

CF1792F

学习了在线卷积。

就首先一定能知道的是，它要算的是正图和补图之间的一些关系。所有情况都该是一一映射，去掉全涂这种特殊不合法情况之后，那么感觉就是要算答案再除二的序列。通过样例可知，中间有两项是，丢到 oeis 上立刻得出了答案序列的所有东西。序列递推式是，EGF 满足，这样就会存在三种做法。

第一种是直接递推式出发，这是个典型的在线卷积。而在线卷积的做法是，考虑已经算完了，接下来要算，对于的位置而言，它由卷积过来，一定有，所以分三类，第一类是，这是直接卷积。第二类和第三类类似，即，此时已知，未知，那么就是半在线卷积。也就算完了在线卷积，时间复杂度。

第二种是考虑 GF，注意到牛迭是完全可行的，时间复杂度。

第三种是拉反，我们重温一下拉反的形式。

设都是的形式幂级数，且。存在唯一的形式幂级数满足，于是有

$[t^n]f(u(t))=\frac{1}{n}[u^{n-1}] f'(u)\phi(u)^n.$

一阵推导，就是要求

$\frac{1}{n}[x^{n-1}](\frac{x}{2x-e^{x-1}-1})^n$

一通操作即可。时间复杂度。

ARC154F

学了个小技巧。

考虑还剩到的和式，假设要算次幂，容易得到是，面对的形式，一律使用 EGF，即定义和式的 EGF 为，一通化简可以得到为。于是我们可以知道总的 EGF 就是

$\prod_{d=1}^n \frac{d}{n}\times\frac{e^x}{1-\frac{n-d}{n}e^x}$

我们要求这个 GF 的，那就是要求出 GF 的前项。如果我们先求出了

$\prod_{d=1}^n \frac{d}{n}\times\frac{x}{1-\frac{n-d}{n}x}$

那么会得到，发现存在问题，因为此时远处项也会对有贡献，但是中就不会出现这种情况，所以我们先求

$\prod_{d=1}^n \frac{d}{n}\times\frac{x+1}{1-\frac{n-d}{n}(x+1)}$

这是分治 FFT 容易算出来的，此刻我们就有了，我们只需要前项，于是就等于求出了

$\sum_{i=0}^{m} a_i(e^x-1)^i$

将其拆出来，得到

$\sum_{i=0}^{m} b_i(e^x)^i$

而，这分母是个常数，而分子等价于，于是等价于求

$\sum_{i=0}^m \frac{b_i}{1-ix}$

这也是分治 FFT 模拟通分过程容易求出的，时间复杂度。

2023.1.27

loj3275

挺麻烦的一道简单题。

容易注意到双向边构成的连通块是团，团是可以缩点的，因为团里每个点的后续情况将会是一样的。那么接下来就是维护连通块合并的过程，我原本想着直接维护 out_size 来计算，发现大的团就无法更新了。合理的做法是用 set 直接维护真实的点，这样更新时就不会算重了。注意到一条边可能构成很多连通块合并，所以要递归下去计算。时间复杂度。

CF1613D

挺简单的一道 dp 题。

注意到一个序列的合法性只与末尾、以及最大数有关，这是因为的限制。设表示序列为，最大数是的方案数。转移是容易的。时间复杂度。

CF833B

简单的线段树优化 dp。

容易知道区间统计颜色数的方法是记录或，发现这个 dp 转移对的拓扑序是独立的，考虑线段树优化这个过程即可。时间复杂度。

CF490F

有好多做法的一道题。

上来容易想到线段树合并，也即整体 dp。但由于要维护两棵线段树我就没写这做法。

将答案写进状态，把序列末尾的数写进 dp 值后，状态的第二维就不会超过高度了。于是可以长链剖分。

两者时间复杂度都是。

CF1156F

为什么这种签到题都有呢？

一眼表示已经用完了的数字，用了个的概率，转移就是，一眼前缀和优化。答案就是每个再取一遍自己，时间复杂度。

2023.1.28

CF1758D

当时没想出来哎。

namespace MAIN {
	inline void MAIN(const int &Case) {
		int n=read();
		if(n&1){
			for(int i=(n-1)/2+2;i<=n;i++)printf("%d ",i);
			for(int i=n+3;i<=n+(n-1)/2+3;i++)printf("%d ",i);
			puts("");
		}
		else {
			for(int i=n-n/2;i<n;i++)printf("%d ",i);
			for(int i=n+1;i<=n+n/2;i++)printf("%d ",i);
			puts("");
		}
	}
}

2022 Shenyang

题解在队伍训练总结中。

2023.1.29

loj3280

点分治模板题。

注意到题意等价于选出若干颜色的点集，使得它们构成连通块。如果我们枚举某一个颜色属于点集，则一路暴力扩展可以知道答案。但这样的复杂度不对，所以我们需要去优化枚举连通块的过程，这个过程就用点分治来优化。点分治的原理是枚举一个点，然后只考虑当前连通集中包含该点的连通块。利用重心，我们可以保证每次连通集大小减半，所以只有层，同时也可以证明这样的枚举是不重不漏的，这就是点分治的真实含义。时间复杂度。