首页 > 笔记 > FFT应用总结

FFT应用总结

只是一些简单的应用,更难一点的还没写完。。

感觉在学校没啥效率,整天瞎考试

bzoj3527

题意

给出$n$个$q_i$,且

$$F_j = \sum_{i< j}{q_iq_j\over (i - j)^2}-\sum_{i>j}{q_iq_j\over (i - j)^2}$$

求$E_i = {F_i\over q_i}$

题解

首先把$i,j$调一下,看着太难受了

$$F_i = \sum_{j< i}{q_iq_j\over (j - i)^2}-\sum_{j>i}{q_iq_j\over (j - i)^2}$$

这样就可以化式子了
$$
\begin{aligned}
E_i &= {F_i \over q_i}\\
&=\sum_{j< i}{q_j\over (j - i)^2}-\sum_{j>i}{q_j\over (j - i)^2}\\
&=\sum_{j=1}^{i-1}{q_j\over (j - i)^2}-\sum_{j=i+1}^n{q_j\over (j - i)^2}\\
&设 g_i = {1\over i^2}\;\;\; f_i = q_i\\
E_i &=\sum_{j=1}^{i-1}{f_jg_{i - j}}-\sum_{j=i+1}^n{f_jg_{j - i}}\\
\end{aligned}
$$

左边的式子显然是个卷积,现在看下右边的式子

$$\sum_{j = i+1}^nf_jg_{j - i}$$

可以换个元

$$\sum_{j + i = i+1}^nf_{j + i}g_{j + i - i}$$

等式两边同时减掉一个$i$。($g_0 = 0$可以直接化)

$$\sum_{j = 0}^{n -i}f_{j+i}g_j$$

再换元

$$\sum_{n-i-j=0}^{n-i}f_{n-i-j+i}g_{n-i-j}$$

化成

$$\sum_{j=0}^{n-i}f_{n-j}g_{n-i-j}$$

设$t = n-i$

$$\sum_{j = 0}^tf_{n-j}g_{t-j}$$

设$f'_i = f_{n-i}$

$$\sum_{j=0}^t f'_jg_{t-j}$$

。。

bzoj 2194

题意

$$c_k=\sum_{k\leq i< n}a_ib_{i-k}$$

题解

化式子吧。。
$$
\large
\begin{aligned}
c_k &= \sum_{k \leq i \leq n-1}a_ib_{i-k}\\
&= \sum_{0\leq i-k \leq n-k-1} a_ib_{i-k}\\
&= \sum_{0 \leq j \leq n-k-1} a_{j+k}b_j \;\;\;\;(j=i-k)\\
& 设 \; N=n-k-1,c'_N=c_k\\
c'_N &= \sum_{0 \leq j\leq N}a_{n-1-(N-j)}b_j\\
& 设 \; a'_{N-j}=a_{n-1-(N-j)},a'_{i}=a_{n-1-i}\\
c'_N &= \sum_{0 \leq j\leq N}a'_{N-j}b_j
\end{aligned}
$$

。。

bzoj 3771

题意

给出$n$个物品,价值为别为$X_i$且各不相同,现在可以取$1$个、$2$个或$3$个,问每种价值和有几种情况?

*顺序不同算一种

题解

构造三个生成函数,系数是这个数出现了几次。$A$表示每种物品取一个的情况,$B$表示每种物品取二个的情况,$C$表示每种物品取三个的情况。

也就是对于每种物品价值$X_i$,A[Xi]++,B[2 * Xi]++,C[3 * Xi]++

如果取$1$个物品,答案就是$A$。

如果取$2$个物品,$A^2$中有重复的$(X_i,X_i)$的情况,所以答案为$A^2-B$。

如果取$3$个物品,$A^3$中可能有$(X_i,X_i,X_i)(X_i,X_i,Y_i)(X_i,Y_i,X_i)(Y_i,X_i,X_i)$这几种重复的情况,而$A\times B$能够求出所有形容$(X_i,X_i,X_i)$和$(X_i,Y_i,Y_i)$的情况数。$(X_i,X_i,Y_i)(X_i,Y_i,X_i)(Y_i,X_i,X_i)$总的情况数=$(X_i,Y_i,Y_i)\times 3$,而$A\times B\times3$又会多减去了两次$(X_i,X_i,X_i)$,所以要用$C$加回来。所以答案为$A^3-3\times B\times A+2\times C$。又由于顺序不同算一种情况,因为每种物品价值都不一样,情况(2)/2,情况(3)/6。

总答案就是

$${A^3(x)-3A(x)·B(x)+2C(x)\over 6}+{A^2(x)-B(x)\over 2}+A(x)$$

注意可以一直用点值表达式形式算。

bzoj 3513

题解

因为$a_i$的范围很小,可以搞个权值多项式,$A_i$表示长度为$i$的木棒出现了多少次

现在考虑求一个$B_i$表示两根木棒拼起来的权值多项式,显然

$$B_i = \sum A_j \times A_{i-j}$$

这是一个卷积的形式,直接fft求解

然后发现这样会出现自己和自己拼起来的情况,直接减掉即可

现在考虑求一下答案的补集,就是不能拼成三角形的情况,再拿1减掉就是答案。

我们对$B$求一个前缀和,那么$B_i$就表示了两根木棒拼起来小于等于$i$的有多少个

那么答案的补集就是$B_i\times A_i$,就是原始长度为$i$的个数乘上拼起来长度小于等于它的个数

因为能正着和倒着拼,所以要除2。最后别忘了除$C_n^3$,我们求的是概率。

bzoj 4259

题解

首先我们定义一个字符串的距离函数,对于两个长度都是$n$的字符串$A,B$,定义他们的距离为

$$dis(A,B) = \sum_{i = 0}^{n-1}(A_i - B_i)^2 [A_i != *][B_i!=*]$$

假如我们把所有星号都约定成$0$的话

$$dis(A,B) = \sum_{i = 0}^{n - 1}(A_i-B_i)^2A_iB_i$$

对于题目的话,首先发现题面里面写到$1\leq m\leq n\leq 300000$,也就是说第二个串要比第一个串要长

那么我们可以枚举第二个串的结尾位置来匹配,定义函数$f_i = dis(A,B[i - m + 1,i])$,那么

$$f_i = \sum_{i = 0}^{m - 1} (A_j - B_{i - m + 1 + j})^2A_jB_{i - m + 1 + j}$$

也就是,$f_i = 0$的时候表明$B$的这个子串和$A$成功匹配了

但是我们想凑出个卷积该怎么办呢?首先式子里面应该有个$i - j$,要构造出来一个的话必须把一个串翻转一下,那我们就把$A$串翻转一下。还有就是$B$的下标有点乱,需要化简一下。我们现在是一个枚举长度$m$,但是我们可以在$A$后面添加很多个$0$,让它变成一个枚举$i$的式子,这样就非常符合卷积的形式了:
$$
\begin{aligned}
f_i &= \sum_{j = 0}^i(A_j - B_{i - j})^2A_jB_{i - j}\\
&=\sum_{j = 0}^i(A_j^2-2A_jB_{i - j} + B_{i - j}^2)A_jB_{i - j}\\
&=\sum_{j = 0}^iA_j^3B_{i - j}-2\sum_{j = 0}^iA_j^2B_{i - j}^2+\sum_{j = 0}^iA_jB_{i - j}^3\\
\end{aligned}
$$

。。

bzoj3509

题解

首先简单化下式子,发现$2A_j=A_i+A_k$

也就是说一个数在两边选两个数使得两数的和为这个数的两倍。

这样对这个数两边的数放到权值生成函数里面,fft一下再找这个数的两倍就可以了。

发现太慢了,$O(n^2\log n)$(这里就把$a_i$最大值也设成$n$了,懒)

这样就可以想到分块的思想,对于块内的暴力一下,块外的fft求下,就可以了。

算下复杂度是$O(\sqrt n \;n\log n+\sqrt n\; n)$

(需要有优越的调参技术


1 COMMENT

  1. Fop_zz2018-03-13 上午11:37

    资瓷啊

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×