Submission #1134526

---

Source Code Expand

#include <cstdio>
#include <complex>
#include <cmath>

int m;
int k;

typedef std::complex<double> complex;

complex C[1<<18];
complex w[1<<17];

unsigned clp2(unsigned x) {
   x = x - 1;
   x = x | (x >> 1);
   x = x | (x >> 2);
   x = x | (x >> 4);
   x = x | (x >> 8);
   x = x | (x >>16);
   return x + 1;
}

unsigned increv(unsigned x) {
   unsigned mm=m/2;
   x = x ^ mm;
   while (x < mm) {
     mm >>= 1;
     x = x ^ mm;
   }
   return x;
}

void fft(complex *A){
  int u = 1;
  int v = m/2;
  for(int i=k;i>0;i--){
    for(int jh=0;jh<u;jh++){
      complex wj = w[jh];
      for(int j = jh << i, je = j|v;j<je; j++){
        complex Ajv = wj * A[j|v];
        A[j|v]  = A[j] - Ajv;
        A[j]   += Ajv;
      }
    }
    u <<= 1;
    v >>= 1;
  }
}

void ifft(complex *A){
  int u = m/2;
  int v = 1;
  for(int i=1;i<=k;i++){
    for(int jh=0;jh<u;jh++){
      complex wj = std::conj(w[jh]);
      for(int j = jh << i, je = j|v;j<je; j++){
        complex Ajv = A[j] - A[j|v];
        A[j] += A[j|v];
        A[j|v] = wj * Ajv;
      }
    }
    u >>= 1;
    v <<= 1;
  }
}

void genw(int i, int b, complex z){
  if(b == 0)
    w[i] = z;
  else {
    genw(i, b>>1, z);
    genw(i|b, b>>1, z*w[b]);
  }
}

int main(){
  int n;
  std::scanf("%d", &n);
  for(int i=1;i<=n;i++){
    int a, b;
    std::scanf(" %d %d", &a, &b);
    C[i].real(a);
    C[i].imag(b);
  }
  m = clp2(n+1) << 1;
  k = __builtin_ctz(m);
  double arg = -2*M_PI/m;
  for(int i=1, j=m/4; j; i<<=1, j>>=1){
    double argj = arg * j;
    w[i].real(std::cos(argj));
    w[i].imag(std::sin(argj));
  }
  genw(0, m/4, 1);
  fft(C);
  C[0] = C[0].real() * C[0].imag();
  for(int i=m/2, j=m-1;i!=(m/2|1);j=(~i&(m-1)),i=increv(i)){
    C[i] = (C[i] + std::conj(C[j]))*(C[i] - std::conj(C[j]));
    C[j].real(C[i].imag()/4.0);
    C[j].imag(C[i].real()/4.0);
    C[i].real(C[j].real());
    C[i].imag(-C[j].imag());
  }
  ifft(C);
  for(int i=1;i<=2*n;i++){
    std::printf("%d\n", (int) ((C[i].real()+0.5)/m));
  }
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:78:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   std::scanf("%d", &n);
                       ^
./Main.cpp:81:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     std::scanf(" %d %d", &a, &b);
                                 ^

Judge Result