标签 FFT 下的文章

FFT NTT小结

给定$a_i,b_i$，定义$c_n=\sum_{i=0}^n a_ib_{n-i}$,求$c$序列。

生地会考后发现自己连NTT的板子都不会打了....

果然是好久没写代码了...

准备重新学习FFT和NTT和FWT

显然，我参加了这次HNOI。

然而并没有什么用，只拿了纯良心的70pts暴力。

30%的数据满足n≤500, m≤10；

70%的数据满足n≤5000；

100%的数据满足1≤n≤50000, 1≤m≤100, 1≤ai≤m。

并不知道在$30pts$ $m\le 10$的基础上，为什么$100 pts$ $m\le 100$，包括$70 pts$ $m\le 100$，然而后面两个部分分真的m可以开到很大。

显然手环2亮度减c和手环1亮度+c是等价的，所以修改相当于在手环2亮度+c$(|c| \le m)$（显然）

假设下标从0开始到n-1(原题为从1到n)