差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:2021年度训练计划及训练记录:lgwza:快速傅里叶变换_fft [2021/02/12 22:21]
lgwza 创建
+++ 2020-2021:teams:legal_string:2021年度训练计划及训练记录:lgwza:快速傅里叶变换_fft [2021/02/15 11:27] (当前版本)
lgwza
@@ 行 17: / 行 17: @@
 === 题解 ===
-通过 $DFT$ 和 $IDFT$ 两个过程，实现多项式由系数表示法 -> 点值表示法 -> 系数表示法。利用单位根的性质实现奇偶分治过程，时间复杂度 $O(n\log n)$。其中递归的分治过程时空消耗较大，通过蝴蝶变换找到各项系数（点值）分治后的位置，直接往上迭代，实现优化。
+通过 DFT 和 IDFT 两个过程，实现多项式由系数表示法 -> 点值表示法 -> 系数表示法。利用单位根的性质实现奇偶分治过程，时间复杂度 $O(n\log n)$。其中递归的分治过程时空消耗较大，通过蝴蝶变换找到各项系数（点值）分治后的位置，直接往上迭代，实现优化。
 === 评价 ===
@@ 行 148: / 行 148: @@
     for(int i=n+m;i>=0;i--)
         printf("%d",c[i]);
+    return 0;
+}
+</code>
+</hidden>
+==== 例 3 ====
+=== 题意 ===
+[[https://www.luogu.com.cn/problem/P3338|P3338 [ZJOI2014]力]]
+给出 $n$ 个数 $q_1,q_2,\cdots,q_n$，定义 $$
+F_j=\sum_{i=1}^{j-1}\frac{q_i\times q_j}{(i-j)^2}-\sum_{i=j+1}^{n}\frac{q_i\times q_j}{(i-j)^2}\\
+E_i=\frac{F_i}{q_i}
+$$ 对 $1\le i\le n$，求 $E_i$ 的值。
+=== 题解 ===
+对题目式子进行化简，可得 $$
+E_j=\sum_{i=1}^{j-1}\frac{q_i}{(i-j)^2}-\sum_{i=j+1}^{n}\frac{q_i}{(i-j)^2}
+$$ 令 $a_i=q_i,b_i=\frac{1}{i^2},a_0=b_0=0,$ $$
+E_j=\sum_{i=0}^{j}a[i]b[j-i]-\sum_{i=j}^{n}a[i]b[i-j]
+$$ 注意到左边已化成卷积形式，现对右边进行转化， $$
+\sum_{i=j}^{n}a[i]b[i-j]=\sum_{i=0}^{n-j}a[i+j]b[i]
+$$ 令 $c[i]=a[n-i]$ （翻转变换），得 $$
+\sum_{i=0}^{n-j}c[n-i-j]b[i]
+$$ 令 $t=n-j$，得 $$
+\sum_{i=0}^{t}c[t-i]b[i]
+$$ 至此，右边也化为了卷积形式。
+令 $f(x)=\sum_{i=0}^na_ix^i,g(x)=\sum_{i=0}^nb_ix^i,h(x)=\sum_{i=0}^nc_ix^i$，答案即为 $E_j=[x^j](f(x)g(x))-[x^{n-j}](g(x)h(x))$。
+用 FFT 做多项式乘法即可，时间复杂度 $O(n\log n)$
+=== 评价 ===
+主要考察推式子能力，将式子转化为卷积形式，再套用 FFT 加速多项式乘法。
+=== 代码 ===
+<hidden>
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+const int N=1e5+5;
+int rev[N<<2];
+typedef complex<double> Comp;
+const double PI=acos(-1.0);
+Comp a[N<<2],b[N<<2],c[N<<2];
+void FFT(Comp *y,int len,int on){
+    for(int i=0;i<len;i++)
+        if(i<rev[i])
+            swap(y[i],y[rev[i]]);
+    for(int mid=1;mid<len;mid<<=1){
+        Comp wn(cos(PI/mid),sin(on*PI/mid));
+        for(int j=0,R=mid<<1;j<len;j+=R){
+            Comp w(1,0);
+            for(int k=0;k<mid;k++,w=w*wn){
+                Comp u=y[j+k];
+                Comp t=w*y[j+k+mid];
+                y[j+k]=u+t;
+                y[j+k+mid]=u-t;
+            }
+        }
+    }
+    if(on==-1)
+        for(int i=0;i<len;i++)
+            y[i]={real(y[i])/len,imag(y[i])};
+}
+int main(){
+    int n;
+    scanf("%d",&n);
+    a[0]=b[0]=c[n]={0,0};
+    for(int i=1;i<=n;i++){
+        double q;
+        scanf("%lf",&q);
+        c[n-i]=a[i]={q,0};
+        b[i]={(double)1.0/i/i,0};
+    }
+    int len=1,l=0;
+    while(len<=n+n) len<<=1,l++;
+    for(int i=0;i<len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
+    FFT(a,len,1);
+    FFT(b,len,1);
+    FFT(c,len,1);
+    for(int i=0;i<=len;i++){
+        a[i]=a[i]*b[i];
+        c[i]=c[i]*b[i];
+    }
+    FFT(a,len,-1);
+    FFT(c,len,-1);
+    for(int j=1;j<=n;j++){
+        printf("%.3f\n",real(a[j])-real(c[n-j]));
+    }
     return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具