【笔记】线图 / Line graph

Posted on

在图论中,一张无向图的线图是能体现其连边状态的一种生成图。有关线图的中文资料很少,但有关它的外文资料非常丰富。在这篇文章中,我将简单介绍线图的定义,以及提出计算线图最小生成树大小的一种方法。

【笔记】从傅里叶变换到数论变换

Posted on

我们可以使用傅里叶变换来快速计算卷积。然而快速傅立叶变换具有一些实现上的缺点,我们必须做复数而且是浮点数的运算,因此计算量会比较大,而且浮点数运算产生的误差会比较大。
这个问题可以用数论变换解决。在模意义下,一些整数可以发挥单位复根的作用,使我们更精确地计算只有整数参加的卷积运算结果。