图论模板 并查集 struct dsu { private: // number of nodes int n; // root node: -1 * component size // otherwise: parent std::vector<int> pa; public: dsu(int n_ = 0) : n(n_), pa(n_,…

FFT解决字符串匹配问题 朴素的字符串匹配 设有两个字符串 $a,b$ 长度分别为 $n,m(n\geq m)$ ，询问字符串 $b$ 在 $a$ 中出现了几次。 这是一个最基础的字符串匹配问题，显然我们容易想到 $O(nm)$ 的暴力匹配方法，同时也可以使用 $KMP$ 算法在 $O(n+m)$ 的复杂度下解决该问题。实际上，我们还可以利用 $F…

ZONe Energy Programming Contest 题解 [toc] AC代码 A - UFO Invasion B - Sign of Friendship C - MAD TEAM 有 $N$ 个人，每个人有 $A,B,C,D,E$ 五个属性，选择 $3$ 个人组成一个团队去参加比赛，这个团队的五项属性定义为每项属性中三个人的最大值…

线性代数模板 高斯消元法 /* * 高斯-约旦消元法 * 可以修改为解异或方程组 修改策略为 * a+b -> a^b * a-b -> a^b * a*b -> a&b * a/b -> a*(b==1) * */ void gauss(int n) { vector<bool> vis(n, fals…

数论常用模板和一些经典问题 简单的防爆模板 namespace SimpleModInt { constexpr int md = (int)1e9 + 7; inline int norm(long long a) { return (a % md + md) % md; } inline int add(int a, int b) { a +=…

ABC199 题解 [toc] AC代码 A - Square Inequality B - Intersection C - IPFL 给定一个字符串 $s$ ，有两种操作： 交换两个字符； 交换前一半字符和后一半字符。 $q$ 次操作后，问最终的字符串。 设置一个标志位记录操作 $2$ 的奇偶，若为偶则正常执行操作 $1$ ；若为奇，则执行操作…

Hello world!