fft – Tgotp-Blog

D. Fuzzy Search

fft下标一定要从0开始,不然特麻烦
观察题目容易发现,可以在O(n)时间内判断对于位置i是否能在[i-k,i+k]区间存在 A G C T
然后得到一个O(n*m)的算法,考虑优化
那么分开考虑 A G C T,令s[i]表示在第i个位[......]

Read more

3992: [SDOI2015]序列统计

容易列出dp方程f[i][j]表示第i个位置乘积为j的方案数。
那么推出转移 f[i+1][j*p\%m] += f[i][j]
此时复杂度O(n*m^2) 显然不能接受
想到对于n特别大的情况一般都会用快速幂。
那么可以列出一个m*m的矩阵进行转移,[......]

Read more

BZOJ3527: [Zjoi2014]力

除以pi化为两个卷积形式,搞一搞就好了。

read more: http://tgotp.science/fft%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/

c++代码如下:

 [......]

Read more

bzoj2194: 快速傅立叶之二

模板题。更多内容见:http://tgotp.science/fft%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/

c++代码如下:

 

【bzoj2179】FFT快速傅立叶

板子题。

更多内容移步http://tgotp.science/fft%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/

c++代码如下:

 

fft学习笔记

学习网站:

http://tieba.baidu.com/p/2513502552?see_lz=1

http://picks.logdown.com/posts/177631-fast-fourier-transform

fft很早以前大概学过,但是其实根本没理解,然后现在重学。[......]

Read more