KeBlog

The OI Algorithm Blog of Kewth

0%

发表于 更新于 分类于

快速沃尔什变换，简称 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 便是求这类卷积的快速算法。

阅读全文 »

发表于 更新于 分类于

淦。

Skip 掉 A ，直接开 C1 。

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

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

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

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

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

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

学傻了.jpg

阅读全文 »

发表于 更新于 分类于

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

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

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

以下运算皆指模 \(p\) 意义下的运算。

阅读全文 »

发表于 更新于 分类于

开场 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 等比赛要高}\)

发表于 更新于 分类于

莫队算法可以通过单点增量的方式以 \(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)\) 次查询。

参考实现：

1
2
3
4
5
// 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})\) 次查询。

参考实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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]);
}

发表于 更新于 分类于

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

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

杜教筛

篇幅过长，点击此处。

min25

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

理论

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

min25 筛可大致分为两步。

阅读全文 »

发表于 更新于 分类于

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

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+ 的好成绩，掉分预定。

发表于 更新于 分类于

以后打比赛写总结。

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

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 的常用技巧和方法。
RMQ 真是流皮，每次深入思考都会有新的发现，所以有了新的发现会更新。

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

一般性普通做法

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

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

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

阅读全文 »

发表于 更新于

所谓博客，都是孤芳自赏。

由于 .github.io 实在太慢，搞了个还是很慢的镜像站：https://kewth.netlify.app/ 。

没什么好说的，动态博客用烦了，搞了好多花里胡哨的东西，还是沉下心来，好好写博客，既然如此，就不打算做什么美化了，基本能用就行，勿喷。

如果公式渲染有问题，请右键公式，点击：math settings -> math renderer -> common html 。

还有日期为 2019.10.01 的都是旧博客直接搬的，并非真实日期，越早期的文章格式可能越屑。

可是我控制不住我记几啊，总感觉不顺眼，实在忍不住去折腾 QwQ

阅读全文 »