快速傅立叶变换应用(FFT Applications)

标签：log 1x FFT 整数 三元组 Applications 傅立叶 当且

1. 3-SUM

1.1 问题描述

Given three sets \(X\), \(Y\), and $Z $ of \(n\) integers each, determine whether there is a triple \(i \in X, j \in Y, k \in Z\) such that \(i + j = k\).

给定三个包含\(n\)个整数的集合, 每个整数的值都在\(0\)到\(m\)之间, 判断是否有一个三元组\((i, j, k)\)满足\(i \in X, j \in Y, k \in Z\)并且\(i + j = k\).

1.2 解答

• 构造多项式:

\[A(x)=a_0x+a_1x+\dots+a_mx^m \\ B(x)=b_0x+b_1x+\dots+b_mx^m \]

其中\(a_i=1\) 当且仅当\(i \in X\), \(b_j=1\) 当且仅当\(j \in Y\).

• 计算\(C(x)=A(x)\times B(x)\). (利用FFT)
• 系数\(c_k\)表示选择一个整数\(i \in X\)和一个整数\(j\in Y\), 使得他们的和为\(k\)的方法数.
• 对于每一个\(k\in Z\), 判断\(c_k\)是否大于\(0\), 如果存在一个\(k\)满足条件, 说明可以找到一个三元组\((i, j, k)\)满足\(i \in X, j \in Y, k \in Z\)并且\(i + j = k\).

时间复杂度: FFT需要\(O(m\log m)\), 遍历\(Z\)需要\(O(n)\), 总共\(O(m\log m+n)\).

未完待续......

标签：log,1x,FFT,整数,三元组,Applications,傅立叶,当且
From： https://www.cnblogs.com/jjvv/p/17146376.html