algorithm - how can i apply fft in non multiplication problem?

Question

hello i'm trying to apply fft on this problem

i'm tring to optimize O(n^2) operation that found every combination of x[i] and y[j] (0 <= i,j <= N) by fft

but after spending short time on studing fft

but since it is not a multiplication operation,

i wonder whether i can apply fft on these kind of problem

would you give me any way to solve this problem?

i'm sorry for my poor english.

below is wrong answer by me, it spent O(N^2) , just help for understand problem

#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;
}

problem: enter image description here

标签： algorithm