ACM

Preface 参考主要来自 https://cp-algorithms.com/algebra/fft.html, https://en.wikipedia.org/wiki/Discrete_Fourier_transform, https://oi.wiki/math/poly/fft/ 为照顾某OJ 本文例程（杂项除外）C++标准仅需11；板子传送门,题目传送门 定义 多项式$A$的$DFT$即为$A$在各单位根$w_{n, k} = w_n^k = e^{\frac{2 k \pi i}{n}}$之值 $$ \begin{align} \text{DFT}(a_0, a_1, \dots, a_{n-1}) &= (y_0, y_1, \dots, y_{n-1}) \newline &= (A(w_{n, 0}), A(w_{n, 1}), \dots, A(w_{n, n-1})) \newline &= (A(w_n^0), A(w_n^1), \dots, A(w_n^{n-1})) \end{align} $$ $IDFT$ ($InverseDFT$) 即从这些值$(y_0, y_1, \dots, y_{n-1})$恢复多项式$A$的系数 $$ \text{IDFT}(y_0, y_1, \dots, y_{n-1}) = (a_0, a_1, \dots, a_{n-1}) $$ 单位根有以下性质 积性 $$ w_n^n = 1 \newline w_n^{\frac{n}{2}} = -1 \newline w_n^k \ne 1, 0 \lt k \lt n $$...

691C. Row GCD You are given two positive integer sequences $a_1, \ldots, a_n$ and $b_1, \ldots, b_m$. For each $j = 1, \ldots, m$ find the greatest common divisor of $a_1 + b_j, \ldots, a_n + b_j$. 引理： $gcd(x,y) = gcd(x,y-x)$ 引理： 可以拓展到 **数组 $gcd$数值上等于数组差分 $gcd$ **；证明显然，略 注意该命题在数组及其差分上取子数组时上并不成立，如 991F. Typora怎么快速加页面内链接… 记$g_{pfx} = gcd(a_2-a_1,a_3-a_2,…a_n-a_{n-1})$ 于本题利用$gcd(a_1+b_1,a_2+b_1,…a_n+b_1) = gcd(a_1+b1,a_2-a_1,a_3-a_2,…a_n-a_{n-1}) = gcd(a_1 + b_1, g_{pfx})$即可 int main() { fast_io(); /* El Psy Kongroo */ ll n,m; cin >> n >> m; vector<ll> a(n); for (ll& x: a) cin >> x; // gcd(a_1+b_1,a_2+b_1,....

1. Candy Rush TL;DR - 串哈希加速比对 + big hash trick 2023-2024 ACM-ICPC Latin American Regional Programming Contest 官方题解：https://codeforces.com/gym/104736/attachments/download/22730/editorial.pdf 取$C_i$出现频率为向量做前缀和后可发现有效区间频率差为$k \cdot 1_n$；直接比对平摊复杂度为$O(nk\log{n})$,$O(k)$来自于比对本身 而比对可以转换为$O(1)$形式，trick如下： 若 $a,b$ 对应区间有效，一定有：$freq_b = k \cdot 1_n + freq_a$ 而在做前缀和是，可以及时消掉$k \cdot 1_n$项：即为全非$0$时全$-1$ 此时的比对即变成$ hash(freq_b) = hash(freq_a) $ 造一个能$O(1)$更新的$hash$即可让最终复杂度可以变为优秀的$O(nlogn)$ 题解$hash$为$(base^i \cdot c_i)%MOD$ - 避免碰撞可以采用更大int类型或模数，或同code开array于不同base计算后比较 #pragma GCC optimize("O3","unroll-loops","inline") #include "bits/stdc++.h" using namespace std; #define PRED(T,X) [](T const& lhs, T const& rhs) {return X;} typedef long long ll; typedef unsigned long long ull; typedef double lf; typedef long double llf; typedef __int128 i128; typedef unsigned __int128 ui128; typedef pair<ll, ll> II; typedef vector<ll> vec; template<size_t size> using arr = array<ll, size>; const static void fast_io() { ios_base::sync_with_stdio(false); cin....

Treap ATTENTION: 出门左转 https://caterpillow.github.io/byot 谢谢喵 又名笛卡尔树，随机BST；支持$log n$插入，删除，查找及闭包操作(push_up) https://cp-algorithms.com/data_structures/treap.html https://oi.baoshuo.ren/fhq-treap A. std::set 类容器 template<typename T> struct treap { struct node { T key; ll priority; ll l, r; // push_up maintains ll size; }; vector<node> tree; vec free_list; private: void push_up(ll o) { tree[o].size = tree[tree[o].l].size + tree[tree[o].r].size + 1; } II split_by_value(ll o, T const& key) { // 偏序 [<, >=] if (!o) return {0,0}; if (tree[o].key < key) { // 左大右小 auto [ll,rr] = split_by_value(tree[o]....

注: segment_tree 均采用 1-Index 访问； segment_tree::reset(vector&) 中vector为0-Index 242E. XOR on Segment 区间二进制改+lazy传递+二进制trick You’ve got an array $a$, consisting of $n$ integers $a_1, a_2, …, a_n$. You are allowed to perform two operations on this array: Calculate the sum of current array elements on the segment $[l,r]$, that is, count value $a_l + a_{l+1} + … + a_{r}$ Apply the xor operation with a given number x to each array element on the segment $[l,r]$, that is, execute $a_l = a_l \oplus x, a_{l+1} = a_{l+1} \oplus x,…,a_r = a_r \oplus x$ This operation changes exactly $r - l + 1$ array elements....

Preface 参考主要来自《算法竞赛入门经典：训练指南》、OIWiki、CP Algorithms等资源和多方博客、课程，在自己的码风下所著 注： 部分实现可能用到较新语言特性，烦请修改后在较老OJ上使用；原则上提供的代码兼容符合Cpp20及以上标准的编译器 Header #include "bits/stdc++.h" using namespace std; typedef long long ll; typedef double lf; typedef pair<ll, ll> II; typedef vector<ll> vec; const inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(0u); cout.tie(0u); } const lf PI = acos(-1); const lf EPS = 1e-8; const ll INF = 1e18; const ll MOD = 1e9 + 7; const ll DIM = 1e5; int main() { fast_io(); /* El Psy Kongroo */ return 0; } Misc 开启GCC debug容器: add_compile_definitions(-D_GLIBCXX_DEBUG) 数学 快速幂 // 注：爆int64考虑__int128或相关intrinsic // MSVC: https://codeforces....

Preface 以下Code为Cpp 版本的直接移植；请考虑前者为上游及第一参考源 Python 实现，一般地优先考虑动态开内存和哈希化查找(e.g. defaultdict代替线性存储) Code部分未加分类，还请善用Cpp 版本 + Ctrl-F Header from collections import defaultdict 图论 领接表 class graph(defaultdict): def __init__(self): super().__init__(list) def add_edge(self, u, v): self[u].append(v) DSU class dsu(dict): def __getitem__(self, key): if not key in self: super().__setitem__(key, key) return super().__getitem__(key) def find(self, u): if self[u] != u: return self.find(self[u]) return self[u] def join(self, u, v): self[self.find(u)] = self.find(v) def same(self, u, v): return self.find(u) == self.find(v) HLD class HLD: def __init__(self, g: graph = None): self....