体验了一段时间的copilot，是时候来写个简单的总结了。

copilot是什么

copilot是一个vscode的插件。最初收到这个消息的时候，我就去申请参与内测，可能那时候已经晚了，一直等到公测才用上。它是一款自动提示插件，不过它的自动提示能力远超以前用过的，一用上，就把我惊艳到了，不是一般的函数名完成，或成员提示，而是一整段代码给你提示完成，甚至在尝试猜测你想要写的功能，直接给你补完一个函数甚至一个类。

先来看几个补全效果图:

以上没有行号灰色部分就是自动补全的部分，你给出函数名，它就猜出你应该要的代码的效果，那以下来一个更复杂点的排序，当然也是没有问题的。

不止如此，你只要写上接下来的函数的注释，有一些它也能直接给你补完这个函数的实现，你的注释还能帮助它提供更准确的信息。所以这又一次说明注释的作用，不但是给人看的，不但是用来生成自动化文档的，甚至是用来自动生成代码的。

近期在折腾SSD、SD、U盘，折腾差不多来写个总结，坑不少。本文部分内容会随着时间而变化，于2021年12月编写。

常见NAND硬件

用于储存的基于NAND的硬件，有SD卡、MicroSD卡，U盘，移动固态硬盘，固态硬盘，通常来说，SD卡这类体积小的速度最慢，U盘次之，再就是移动固态硬盘，最快是固态硬盘。之所以说通常，因为还要看接口和协议速度。

颗粒品质，原片、白片、黑片

储存颗粒按品质划分可以分为三大类，原片、白片、黑片。原片就是品质最好的，原厂最严格标准下的产品，白片就是从晶圆上不及格的里面，把还相对较好的挑选出来，黑片就是白片也不如，在剩下的挑选还能用的，同时把坏区进行屏蔽后造出来的颗粒，某宝上特别便宜的U盘肯定是黑片，还有像MP3，玩具等，通常都是用的黑片。黑片寿命说不准，快的一个星期，慢的2年，看运气。

颗粒类型，SLC、MLC、TLC、QLC、3D NAND

SLC表示，一个存储单元，只存0和1，即1bit，MLC保存00、01、10、11，即2bits，同理，TLC可以保存3bits，QLC保存4bits。SLC最贵，速度最快，寿命最长，可达10W次擦除（原片颗粒的情况下，不算白片黑片，下同）。MLC次之，约3000到5000次擦除。TLC再次之，约1000次擦除。QLC速度最慢，寿命最短，约800次擦除。另外，3D NAND可以大幅度提升寿命，3D TLC可达3000到5000次擦除，3D QLC可达1000到3000次擦除。

近期在折腾linux，折腾差不多来写个总结，这货折腾了我很长的时间。由于USB3.0已经发展很久了，现在随便买的MicroSD/SD卡或U盘基本上都是USB3.0 class 10起步，所以考虑直接用这些来安装系统，这样你对哪个系统不满意直接换个U盘或SD卡就搞定了，而且测试下来速度也不慢。即使你的机器只有USB2.0接口，那也是能用的，就是启动时能感觉出来慢一些。这个也是方便咱们在校学生只有一台电脑，能方便更换系统不必每次折腾一次硬盘，同时可以熟悉比赛时所用的linux环境。另外，如果你想偷懒，我在这也准备了一些系统镜像，直接刷入U盘即可使用，请参见本文最末尾。本文主要针对LTS20版ubuntu，存在有效时限。

在USB存储器上安装linux操作系统

在USB设备上安装个linux系统是很容易的，比起windows和MacOS来说，容易很多。这里有两种操作方式，一是使用虚拟机，这样我们只需要准备一个U盘（或SD或MicroSD卡，下文中说的U盘通常指这三者，且容量必须是16G或以上），二是使用真实机器来安装，这样我们需要准备两个U盘，多出来的一个是用来制作安装盘，安装工具推荐 Rufus 和 YUMI 以及 Ventoy，后两者可以用于制作多启动的U盘。

二分搜索虽然基本思想简单，但其细节却令人意外的抓狂（Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky）。这里我们来分析一下常见写法的坑。

两类不同的二分

二分有两类，一是找值，即判断某个值存不存在，二是找边界，前者比后者简单很多，以下是找值的典型写法（来自中文wiki百科）

int binary_search(const int arr[], int start, int end, int key) {
	int ret = -1;       // 未搜索到数据返回-1下标

	int mid;
	while (start <= end) {
		mid = start + (end - start) / 2; //直接平均可能會溢位，所以用此算法
		if (arr[mid] < key)
			start = mid + 1;
		else if (arr[mid] > key)
			end = mid - 1;
		else {            // 最後檢測相等是因為多數搜尋狀況不是大於要不就小於
			ret = mid;  
			break;
		}
	}

	return ret;     // 单一出口
}

对于找边界，有四种情况，如以下例子，查找数值5的四种边界

1 1 1 2 2 5 5 5 5 7 9
        ^ 1 小于的最右元素
          ^ 2 大于等于的最左元素
                ^ 3 小于等于的最右元素
                  ^ 4 大于的最左元素

既然有四种边界，那就有四种写法。

在上一篇介绍了基础优化算法后，本篇介绍更复杂的内容。本篇的三大内容：FFT，NTT，分治除法。中文资料中我尚未发现有博客文章在介绍分治除法的，所以我就来写第一个介绍吧。

FFT (Schönhage–Strassen algorithm)

FFT就是快速傅里叶变换的缩写，FFT这里不重点介绍，参见oiwiki中对FFT的介绍

用比较显浅且简要的方式来介绍的话，FFT可以在$O(nlogn)$时间里（注：严格来说应该是$O(nlognloglogn)$，论文链接在这，在274页7.8处开始证明）求出两个多项式的乘积，而大整数乘法就可以视为两个整数系数的多项式的积再处理进位即可。那这样就产生一个问题，如果这个大整数采用的基数base，且长度为n，那么多项式的积的最大值可能会达到$n(base-1)^2$，因为FFT采用浮点运算，那么这个最大值必须在double的精度内，所以如果采用万进制，那么很容易导致精度不足进而结果错误，另外，还有求单位复根时的误差也会让它提早出现结果错误。实际应用的时候，一般采用10进制来增加长度的上限。所以如果你的大整数采用压位表示，那么在运用FFT之前，要先做拆位拆成10进制。总之，因为浮点精度的问题，不建议在大整数实现里使用FFT，建议采用下文要介绍的NTT来代替。所以这里对FFT的优化不做介绍，重心放在NTT上。

NTT

NTT就是快速数论变换，它和FFT很像，但它在整数域上做变换，具体数学介绍参见oiwiki中对NTT的介绍。由于没有浮点数参与，于是没有精度上的问题。