《万叶集》雷神短歌

记一下《言叶之庭》中两句经典的台词: 隐约雷鸣 阴霾天空 但盼风雨来 能留你在此 隐约雷鸣 阴霾天空 即使天无雨 我亦留此地 查阅原诗集,原文如下: 雷神小动,刺云雨零耶,君将留? 雷神小动,虽不零,吾将留妹留者。 「鸣神の 少しとよみて さし昙り 雨も降らんか 君を留めん」 (なるかみの すこしとよみて さしくもり あめもふらぬか きみをとどめむ) 「鸣神の 少しとよみて 降らずとも 我は止まらん 妹し留めば」 (なるかみの すこしとよみて ふらずとも わはとどまらん いもしとどめば)

FFT算法学习笔记

写在前面     关于学习FFT算法的资料个人最推荐的还是算法导论上的第30章(第三版), 多项式与快速傅里叶变换, 基础知识都讲得很全面     这篇文章即是博主在阅读FFT算法的相关学习资料之后的一些总结, 作为日后复习查阅的材料来源, 同时也可以作为读者学习FFT算法的一份资料 FFT算法基本概念     即快速傅里叶变换, 是离散傅里叶变换的加速算法, 可以在的时间里完成, 利用相似性也可以在同样复杂度的时间里完成逆     即离散傅里叶变换, 这里主要就是多项式的系数向量转换成点值表示的过程     在ACM-ICPC竞赛中, FFT算法常被用来为多项式乘法加速, 即在复杂度内完成多项式乘法, 当然实际应用不仅仅限于这些, 时常出现需要构造多项式相乘来进行计数的问题, 也需要用FFT算法来解决, 相关的几个问题在本文中也会提及