KeBlog

快速沃尔什变换

发表于 2019-11-03 更新于 2020-05-19 分类于算法

快速沃尔什变换，简称 FWT 。

用处

多项式卷积一般是这样的：

\[ C_i = \sum_{j + k = i} A_j \cdot B_k \]

这个可以用 FFT 快速求解。

然而还有一个诡异的卷积：

\[ C_i = \sum_{j \oplus k = i} A_j \cdot B_k \]

其中 $ $ 是任意一种位运算。

FWT 便是求这类卷积的快速算法。

阅读全文 »

cometoj-13

发表于 2019-10-25 更新于 2020-05-19 分类于总结

淦。

Skip 掉 A ，直接开 C1 。

一看卧槽搜索题，果然简单，然后码，然后码挂了，调了一波，在 8min AC 。

然后既然做了 C1 那就继续看 C2 嘛，

一看卧槽煞笔题，果然简单，然后码，然后没码挂，交了一波，
TLE 了 4 个点。。。

回去看 A ，卧槽果然签到题，花 2min A 了。

然而对于 C2 还是一脸懵逼，后来理性分析了复杂度上界，发现用 set 多了个 log ，
想着怎么撸掉这个 log ，卧槽并查集不就行了，几乎重构了一遍，在 41min AC 。

说起来我第一个想到的是用 set 的原因是做过策爷的“基础排序算法练习题”，
那里维护有效点对的方式就是用 set + 二分。
然而这里特殊一点，用过的点不会在出现，直接并查集就好了。

~~学傻了.jpg~~

阅读全文 »

二次剩余

发表于 2019-10-21 更新于 2020-07-22 分类于算法

二次剩余，~~俗称模意义开根~~。
也就是对于常数 $n$ 解这样一个方程：

\[x^2 \equiv n \; (mod \; p)\]

这里只介绍模数 $p$ 为奇素数的解法，也就是 Cipolla 算法。

以下运算皆指模 $p$ 意义下的运算。

阅读全文 »

LGR-061&XR-4

发表于 2019-10-20 更新于 2019-12-06 分类于总结

开场 30min 才反应过来有场比赛。
不知道哪来的自信就去报了 Div.1 。。。

第一次打 IOI 赛制的网络赛，感觉海星，不像 ACM 一样必须 A 题，
打部分分的话就和平时训练的感觉一样，操作起来相对顺手。

~~但是打网络赛为什么要拿部分分呢，当然冲着 A 题去啊是吧~~

然而全场只能做出 A 题。并没有平时打 ACM 赛制的时候有签到题。
不过还好，反正我不适合打手速题。

Skip 掉了 B （还好 Skip 掉了，后来全程肝 B 没肝出来），直接开 C 。
发现 C 的 63' 巨水，打了个神奇剪枝交了一发，我一直感觉这玩意复杂度是 $O(np)$ 的，
但是没用，TLE ，复杂度假了呗，虽然我并不知道原因，但觉得剩下的 37' 性价比不高，就 Skip 掉了。

提答题好评。

洛谷不支持提答题差评。

但是它给的输入文件的坐标都是有理数，小数点后面一堆数我 TM 怎么知道它的具体位置啊，在图里面标注坐标的无理数表示会死吗。。
第一个点蛮简单的，然后第二个点就卡死了。

弃疗，回去肝 B 。

但是我觉得 B 真的难啊，好多细节？反正是没肝出来，最后 173' 狗到 rank21 。

然而这场比赛参加的人少，只有 300+ 个人打，而且好像很多流皮的人都不打洛谷月赛哦，
所以不太理解为什么 XRound 为什么坚持在洛谷办~~（难道是 py 交易？）~~，
平心而论对于 XR 这种比赛 CometOJ 应该是个更合适的平台。

$\color{white}{事实上，洛谷的确为办一场月赛出了不少钱，出题人的待遇比在 cf 等比赛要高}$

莫队二次离线

发表于 2019-10-16 更新于 2020-07-22 分类于算法

莫队算法可以通过单点增量的方式以 $O(n\sqrt{n}K)$ （认为 $n, q$ 同阶）的复杂度离线处理若干区间信息询问。其中每次单点增量，即每次端点移动的复杂度为 $O(K)$ 。

大多数情况下端点移动的复杂度是 $O(1)$ 的，这样的问题一般是统计区间内的“数”。而统计区间内的“数对”这样的问题往往难以 $O(1)$ 处理端点移动。

莫队二次离线或许能处理这样的问题。

什么用

一般莫队有 $O(n\sqrt{n})$ 次端点移动，如果要用数据结构维护信息的话，就有 $O(n\sqrt{n})$ 次修改和 $O(n\sqrt{n})$ 次查询。

而莫队二次离线能够优化为成 $O(n)$ 次修改和 $O(n\sqrt{n})$ 次查询，从而允许使用一些修改复杂度大而查询复杂度小的方式来维护信息。例如分块，如果能 $O(\sqrt{n})$ 修改和 $O(1)$ 查询的话，总的复杂度就是 $O(n\sqrt{n})$ 。

但是有两个前提：

维护的信息有一定可减性，换句话说必须保证每次询问 $[l, r]$ 与 $r + 1$ 产生的贡献时，需要能够用 $[1, r]$ 与 $r + 1$ 产生的贡献减去（或者其他方式）$[1, l)$ 与 $r + 1$ 产生的贡献代替。
维护的信息有一定可加性，换句话说在每次询问前在不知道当前的 Ans 的情况下可以得到 Ans 的改变量（或某种改变方式）。

怎么用

考虑每次右端点右移的过程（右端点左移以及左端点移动是类似的）。

每次右端点 $r$ 从 $r_0$ 移动到 $r_1$ 时，对于其中的每一个 $r$ ，都需要查询 $[l, r - 1]$ 与该点产生的贡献。考虑差分，利用上面提到过的可减性，查询 $[1, r]$ 与 $r + 1$ 产生的贡献和 $[1, l)$ 与 $r + 1$ 产生的贡献。

Part 1

$[1, r]$ 与 $r + 1$ 产生的贡献只与 $r$ 有关，可以记为 $f_r$ 。那么预处理 $f_r$ 只需从小到大一个个加点维护当前的 $[1, r]$ 并询问出 $f_r$ 。

这个过程需要 $O(n)$ 次修改和 $O(n)$ 次查询。

参考实现：

// a[i] 是第 i 个元素
for(int i = 1; i <= n; i ++) {
	f[i] = Query(a[i]);
	Modify(a[i]);
}

另外如果需要卡常，可以将 $f$ 做一遍前缀和，这样后续查询 $[r_0, r_1]$ 总的贡献就可以 $O(1)$ 计算了（不影响复杂度）。

Part 2

$[1, l)$ 与 $r + 1$ 产生的贡献可以二次离线，在 $l$ 处存下 $r + 1$ 之后再考虑计算。这样做的空间复杂度是 $O(n\sqrt{n})$ 的，但事实上每次只需把 $[r_0, r_1]$ 这个区间存进 $l$ 处而不是把每个数存进去就可以做到 $O(n)$ 的空间复杂度了，这样询问的时候也只需求 $[r_0, r_1]$ 整体的贡献，常数上还能少一个 $O(n\sqrt{n})$ 的瓶颈。

离线处理上述的贡献，也和求 $f_r$ 的过程类似，每次从小到大一个个加点维护当前的 $[1, l)$ ，并对于 $l$ 处存下的每一个数逐个询问 $[1, l)$ 与其产生的贡献即可。这个过程需要 $O(n)$ 次修改和 $O(n\sqrt{n})$ 次查询。

参考实现：

int l = 1, r = 1;
for(int i = 1; i <= q; i ++) {
	int L = query[i].l, R = query[i].r; // 排序后的询问
	if(r < R) {
		vector[l].push_back(std::make_pair(r + 1, R));
		r = R;
	}
}

for(int i = 1; i <= n; i ++) {
	for(auto par : vector[i])
		for(int k = par.first; k <= par.second; k ++)
			Query(a[k]); // 这里用什么东西存一下结果就好了
	Modify(a[i]);
}

亚线性筛

发表于 2019-10-15 更新于 2021-03-29 分类于算法

亚线性筛，就是以低于线性的复杂度预处理一些线性信息的筛法统称。

目前我会杜教筛和 min25 还有 powerful number。

杜教筛

篇幅过长，点击此处。

min25

min25 筛是扩展埃氏筛，也可以筛一类（更复杂的）积性函数的前缀和，并且通常是同类亚线性筛中最快的一个。
而且灵活运用 min25 可以处理一些特殊的关于质因子的问题。

理论

假设要求 $S(n) = \sum_{i=1}^n f(i)$ 。

min25 筛可大致分为两步。

阅读全文 »

cf-592div2

发表于 2019-10-13 更新于 2020-05-19 分类于总结

自闭。
这大概是我打过最失败的一场比赛。

~~UPDATE: 我还是太 naive 了，比起后面 Div1 爆零，这次还算好的。~~

A 签到题，然而我在 14min 才 A ，我是真的不适合做手速题。

B 行数开大点就是插头 DP ，然而行数只有 2 ，插头只有 3 种，
随便 DP 一下就行了，中间少考虑一种插头 WA 了一发，在 25min AC 。

然后，就没有然后了。

C 题解二元一次方程的整除解，woc 这不扩欧板题嘛，没想太多，直接码上去。
然后很轻松过了样例啊，交 WA 了，哦没判负数，又交 WA 了。。。
静态查错无果，遂对拍，拍了 1000+ 组全是 AC 。

事情好像不太对劲.jpg

skip 掉，直接开 E ，发现了个单调性，没想太多，直接码上去。
还是很轻松过了样例啊，交 WA 了。
静态查错无果，遂回去调 C 。

冷静分析一波后发现 C 题神 tm 会爆 long long 。
这简单，改 int128 ，结果交 CE 了。
然后就到网上蒯 c++ 大整数模板，贴下来后，
样例都过不去了我天，然后我就去调那个模板，也是醉了。

1
2
3

Big n = 10, x = 5;
std::clog << n << std::endl;
std::clog << n - x + x << std::endl;

上面代码第一行输出 10 ，第二行输出 20 。

当时我心态就炸了，简直想去问候那个把模板贴他博客上的祖宗十八代。
写的这玩意连加减法都算不对心里没点 B 数吗也敢往网上放。

服了，还是乖乖想不爆 long long 的解法吧。

9102 年了还有人靠爆 long long 混饭吃。
这样明显卡语言啊，对 c++ 选手毫无公平性可言。

至于正解，自然是没想出来。

最后获得了 rank3400+ 的好成绩，掉分预定。

cometoj-12

发表于 2019-10-13 更新于 2019-12-06 分类于总结

以后打比赛写总结。

~~话说今天打到短裙好开心啊~~

A 题签到题。

为什么我第一个想的就是 O(1) 的哈希？
表示完全没有去想好写得多的排序，而是直接把三个字符用 int 表示去搞。
然后本地测样例玄学错误，最后发现哈希的数组开小了。
7min 做出 A 题表示自闭。

~~真是可怕交题的时候刷新就有 40+ AC 了~~

B 题还是签到题，以为能在 5min AC 结果打了 9min ，感觉我不适合这种手速题。

然后我 C 题看都没看一眼直接 skip 掉就去开了 D 题。
看了 3min 哇这不数位 DP 吗，现在还没人交，我还有拿一血的想法。
然后打了出来，测样例， woc 过了，这个时候还是 4 提交 0 通过。
我在机房大呼卧槽我要拿一血了，然后自信满满地交了上去。

成功 WA 掉所有点。

再刷新 D 题一血就已经被拿了。

然后我的心路历程是这样的：

我要拿二血。

我要拿三血。

我要拿四血。

算了我凉了还是做好长期打算拿个十血什么的吧。。。

期间各种被 master 嘲讽，各种互怼。

master 走后没人跟我说话了，然后冷静分析了一波，发现限制条件搞错了，
然后随便搓了几行代码就 A 了。

~~所以以后打比赛要远离 master~~
所以以后打比赛还是要在快节奏中冷静下来。

A 完 D 已经是 2h 了，回去看 C ，~~这 tm 不最短路板题嘛~~。
然而 C 题有坑，卡了好久，最后在比赛结束前 3min rush 了一发成功 AC 。

然后靠着 4 题 + 罚时 8h 狗进 rank8 ~~拿到短裙啦~~。

这场比赛绝对是我打的最爽的一场网络赛，感觉 cometoj 的 ACM 比赛才是最刺激的，
题目质量高，节奏快，竞争激烈，尤其是相对于 cf 和 atcoder 来说没有网速杀和题意杀。
体验感极好。
~~最主要的还是有短裙拿~~

然而拿短裙又没人肯女装，我还是选择拿杯子吧。。

RMQ

发表于 2019-10-11 更新于 2020-05-19 分类于算法

总结求各种 RMQ 的常用技巧和方法。
RMQ 真是流皮，每次深入思考都会有新的发现，所以有了新的发现会更新。

以下 n 表示数列的大小，q 表示询问的次数，均以最大值为例。

一般性普通做法

线段树当然是可以在线维护的，复杂度 $O(n + qlogn)$ 。
甚至还可以支持单点修改或区间修改。

但是如果只是静态询问的话，可以用 ST 表预处理后 $O(1)$ 在线处理询问，
复杂度 $O(nlogn + q)$ 。

这两个做法烂大街了，是基础中的基础，不是本文讨论重点。

阅读全文 »

O(1)黑科技

发表于 2019-10-10 更新于 2019-12-06 分类于算法

@CYJian 出了一道黑科技二合一，我就顺便跟着学了学。

O(1) gcd

在 O(V) 的预处理后可以做到 O(1) 查询 gcd ，其中 V 是权值的大小。

主要利用到的一个性质是可以将任意 x 分解为三个数 a * b * c ， a, b, c 分别满足以下两个条件之一：

不超过 $\sqrt{x}$ 。
是质数。

update: 之前写假了，感谢 @CYJian 的 hack 。

zzq 把满足这个性质的分解称为“迷之分解”，那我也这么叫吧。

考虑证明一下，顺便构造一个“迷之分解”。

找到 x 的最小质因子 p ，然后假设已知 x / p 的“迷之分解” A, B, C (A <= B <= C) 。
那么把 p 乘到 A 上就可以得到 x 的“迷之分解” A * p, B, C 。
分类讨论，如果 p 不超过 $\sqrt[4]{x}$ ，由于 A 是 A, B, C 三者中最小的，
一定满足 A 不超过 $\sqrt[3]{x/p}$ ，那么可得：

\[A \cdot p \leq \sqrt[3]{x/p} \cdot p = \sqrt[3]{xp^2} \leq \sqrt{x}\]

而如果 p 超过 $\sqrt[4]{x}$ ，由于 p 是最小质因子，
那么如果 x 的“迷之分解”有合数 C ， C 至少是 $p^2$ ，超过 $\sqrt{x}$ ，
那么 B 的大小就会比 p 小，与 p 是最小质因子矛盾，
因而此时 x 的“迷之分解”全是质数。

“迷之分解”的分析就是这样，通过线性筛可以很好预处理出 O(V) 内的所有数的“迷之分解”。
只需筛出每个数的最小质因子即可按上述方法递推出“迷之分解”。
然后只需预处理出 $O(\sqrt{V})$ 内两两的 gcd ，为了不带 log ，需要递推预处理。
此时求 gcd(x, y) 只需对于 x 的“迷之分解” A, B, C 依次对 y 求 gcd （每次求 gcd 后把 y 除以该 gcd ），
以 A 为例，如果 A 不超过 $\sqrt{x}$ ，直接查表可以得到 gcd(A, y) （查的是 gcd(A mod y, A) ），
否则 A 为质数，简单讨论一下就可以得到 gcd(A, y) 了。

关键部分参考实现：

int magic[maxv][3]; // 每个数的“迷之分解”
int gcd[maxb][maxb]; // 预处理的 gcd
int GCD(int x, int y) {
	int res = 1;
	for(int i = 0; i < 3; i ++) {
		int X = magic[x][i];
		int d;
		if(X < maxb)
			d = gcd[X][y % X];
		else if(y % X)
			d = 1;
		else
			d = X;
		res *= d;
		y /= d;
	}
	return res;
}

O(1) 快速幂

在 $O(\sqrt{p})$ 的预处理后可以做到对于一个固定的底数 O(1) 查询快速幂，
其中 p 是模数（或者上式是 $\sqrt{\phi(p)}$ ），或者是指数的范围。

这个就简单得多，对于每个 $a^k$ 的指数 k 都可以表示为 $a \sqrt{p} + b$ 的形式，
满足 $a, b < \sqrt{p}$ ，分别预处理即可，
即预处理 $a^0, a^1, a^2 ... a^{\sqrt{p}}, a^{2\sqrt{p}}, a^{3\sqrt{p}} ... a^p$ 。