Ff472130

摘要： 前言 优化建图指的是针对大规模边数，利用数据结构或其他技巧建出边数较少的等效图，或直接维护连通性，实现优化复杂度的目的。 有关题目的题单 线段树优化建图 CF786B Legacy 题意 有 \(n\) 个结点的图，有 \(m\) 次操作，每次操作有如下三种加边方法： $u \rightarrow 阅读全文

摘要： FWT 简介 FWT 是用于解决对下标进行位运算卷积问题的方法。 公式：\(c_i= \sum_{i=j \oplus k}a_j b_k\) 其中 \(\oplus\) 是二元位运算中的某一种。 FWT 的原理与 FFT 类似，我们令对数组 \(a\) 经过快速沃尔什变换后记为 \(A\)，那么 阅读全文

摘要： AT_agc076_a [AGC076A] Hamming-Distant Arrays solution: 我们定义第 \(i\) 列的代价为这列出现最多的数的次数减 \(1\)，令其为 \(s_i\)。 先给出结论：满足题意的构造方案的充要条件是 \(\sum_{i=1}^{n^2}s_i < 阅读全文