如何在非乘法类组合运算问题中应用FFT优化O(n²)时间复杂度

需要对遍历所有a∈[0,2^N-1]、b∈[0,2^N-1]的O(4^N)运算做优化，原本期望用FFT实现效率提升，但不确定当前运算是否符合FFT的适用条件，需要可行的优化方案。

#include <iostream>
#include <cmath>
#define MAX 262145
using namespace std;
typedef long long LL;
int N;
LL ans[MAX] = {0,};
LL c[19][2][2] = {0,}; // c [2^i][xi][yi]
int x[] = {0,0,1,1};
int y[] = {0,1,0,1};
LL A[MAX] = {0,}; //Set A
LL B[MAX] = {0,}; //Set B
LL power[18] = {0,}; //power[i] == pow(2,i)
LL cal(LL a,LL b){ // find the index number for input pair(a,b)
   LL res = 0;
   for(int i = 0 ; i < N ; i++){
       res += c[i][(a&(1<<i)) == 0 ? 0 : 1][(b&(1<<i)) == 0 ? 0 : 1] * power[i];
   }
   return res; // the result will point the index of f(x,y)
}
int main() {
   ios_base::sync_with_stdio();
   cin.tie(0);
   cout.tie(0);
   cin >> N;
   string str;
   int mv = pow(2,N);
   for(int i = 0 ; i < N ; i++){
       cin >> str;
       power[i] = pow(2,i);
       for(LL j = 0 ; j < 4 ; j++){
           c[i][x[j]][y[j]] = (int)(str[j] - '0');
       }
   }
   for(int i = 0 ; i < mv ; i++){
       cin >> A[i];
   }
   for(int i = 0 ; i < mv ; i++){
       cin >> B[i];
       if(B[i] != 0){
           for(int j = 0 ; j < mv ; j++){
               if(A[j] != 0){
                   ans[cal(j,i)] += A[j]*B[i]; //
               }        
           }
       }
   } // in this loop we use O(N^2)
   for(int i = 0 ; i < mv ; i++){
       cout << ans[i] << " ";
   }
   return 0;
}

首先明确：你当前的运算不属于加法卷积范畴，确实不适合用FFT优化。该运算属于逐位独立二元运算的广义卷积，使用快速沃尔什-哈达玛变换（FWHT）的自定义变种即可实现优化，复杂度可以从原有O(4^{N)降低到O(N·2}N)，完全适配你给出的代码逻辑。

原理说明 #

• 你的cal(a,b)函数是逐位独立计算的：每一位的输出仅由a和b的对应二进制位、以及该位的c[i]规则决定，不同位之间没有耦合，完全满足FWHT的适用前提。
• 你输入的长度为4的字符串本质是定义了每一位的二元运算映射：例如输入0110就对应异或运算，输入0001对应与运算，FWHT支持为每一位自定义运算规则，完全适配你的需求。

实现步骤 #

1. 为每一位的自定义运算构造对应的FWHT变换矩阵
2. 对数组A和数组B分别执行自定义FWHT变换，得到A'和B'
3. 对应位置相乘得到临时数组C，即C[k] = A'[k] * B'[k]
4. 对数组C执行逆FWHT变换，得到的结果就是你需要的ans数组，可直接替代原有双层循环逻辑。

注意事项 #

• 当前你定义的c[i][x][y]为0/1值，刚好对应常规位运算的映射规则，无需调整变换逻辑；如果后续需要扩展为其他整数取值，只需对应修改变换矩阵的构造规则即可。
• 你设定的MAX规模为262144，对应N最大为18，优化后总运算量仅为18*262144≈470万次，完全可以在普通设备上毫秒级运行。

内容的提问来源于stack exchange，提问作者cicada