FFT习题 2018.5

数学，数论

---

代码见这.

BZOJ.2194.快速傅立叶之二

$Descripiton$
　　给定$A[\ ],B[\ ]$，求

$$C[k]=\sum_{i=k}^{n-1}A[i]*B[i-k]\ (0\leq k<n)$$
$Solution$
　　(先令$n=n-1$)
　　首先往卷积上想。。
　　$i$与$i-k$的差值是一定的，但是卷积的形式是 $$C[k]=\sum_{i=1}^k A[i]*B[k-i]$$
　　即$i$与$k-i$的和是一定的。
　　于是考虑把一个数组反转一下，这里把$B[\ ]$反转，那么 $$C[k]=\sum_{i=k}^n A[i]*B[n+k-i]$$
　　这样$i$与$n+k-i$的和就是一定的了，为$n+k$，于是令 $$D[n+k]=\sum_{i=k}^n A[i]*B[n+k-i]$$
　　这样就可以$FFT$求$D[\ ]$了。
　　 $$D[n+k]=\sum_{i=0}^{n+k}A[i]*B[n+k-i]$$
　　$i=0\sim k-1$和$i=n+1\sim n+k$时，要么$A[i]=0$要么$B[i]=0$，没有影响。
　　所以最后的$C[k]=D[n+k]$。

BZOJ.3527.[ZJOI2014]力

$Descripiton$
　　给出$q[\ ]$，

$$F[j]=\sum_{i<j}\frac{q_iq_j}{(i-j)^2}-\sum_{i>j}\frac{q_iq_j}{(i-j)^2}$$
　　令$E_i=\frac{F_i}{q_i}$，求所有$E[i]$。
$Solution$
　　这的挺详细了，我再写遍。
　　（下标从0开始，$n=n-1$）
　　可以把$q_j$约去，即 $$E_j=\sum_{i=0}^{j-1}\frac{q_i}{(i-j)^2}-\sum_{i=j+1}^n\frac{q_i}{(i-j)^2}$$
　　令$f[i]=q[i]，g[i]=\frac{1}{i^2}$，规定$g[0]=0$，那么
$$E_j=\sum_{i=0}^{j-1}f[i]*g[j-i]-\sum_{i=j+1}^nf[i]*g[j-i]$$
　　（注意是个平方）
　　左边$\sum_{i=0}^{j-1}f[i]*g[j-i]=\sum_{i=0}^{j}f[i]*g[j-i]$就是卷积的形式，可以直接算。
　　右边
$$\begin{aligned} \sum_{i=j+1}^nf[i]*g[j-i]&=\sum_{i=j}^nf[i]*g[j-i]\\ &=\sum_{i=0}^{n-j}f[i+j]*g[i] \end{aligned}$$
　　反转$f[\ ]$，令$h[n-j-i]=f[i+j]$，那么 $$\sum_{i=0}^{n-j}f[i+j]*g[i]=\sum_{i=0}^{n-j}h[n-j-i]*g[i]$$
　　令$X_{n-j}=\sum_{i=0}^{n-j}h[n-j-i]*g[i]$，也用FFT计算就可以了。
　　最后$E_j=\sum_{i=0}^{j-1}f[i]*g[j-i]-X_{n-j}$。

　　还有种常数更优的方法？

CF.528D.Fuzzy Search

$Descripiton$
　　给出文本串S和模式串T和k，S,T为DNA序列(只含$A,T,G,C$)。对于S中的每个位置$i$，只要$s[i-k]\sim s[i+k]$中有一个位置匹配了字符$c$，那么就认为$i$可以匹配$c$。求S中有多少位置匹配了T。
$Solution$
　　题意一直不很明白。。(→→这就是你颓了一下午一晚上写了一道题的理由？)
　　匹配当然是连续的，即若位置$i$匹配，则$S[i+j]=T[j]\ (0\leq j<m)$。
　　我们枚举每个字符c，算出每个位置的$F[j]$，表示当前匹配字符c，$s[j]\sim s[j+m-1]$ 能够和 $T[0]\sim T[m-1]$ 匹配的有多少个。
　　令$f[i]=[位置i可以和当前字符c匹配],g[i]=[\ T[i]==c\ ]$，那么

$$F[j]=\sum_{i=0}^{m-1}f[j+i]*g[i]$$
　　一个位置$i$满足4个字符的$f[i]$之和等于$len(T)$，$i$才是一个合法的位置。(怎么可能$>len(T)$还有T本身限制呢→→)
　　同上一题，反转$g[\ ]$吧，那么 $$F[j]=\sum_{i=0}^{m-1}f[j+i]*g[m-1-i]=G[m-1+j]$$
　　FFT算就行了。
　　$f[i]$的预处理一遍前缀和就行啊。。

$Descripiton$
　　
$Solution$