codechef 3D Queries(MGCH3D)

题外话

这个题是cc 9月challenge的最后一题，当时没仔细考虑，以为这是个近似计算的题。。。赛后看了题解才猛然醒悟

codechef 3D Queries(MGCH3D)

Description

求$\sum_{i!=j} \frac{|A(X_i - X_j) + B(Y_i - Y_j) + C(Z_i - Z_j) + D|}{N(N-1)\sqrt{(X_i-X_j)^4 + (Y_i-Y_j)^4+(Z_i-Z_j)^4}}$
$2\le N \le 777777,1\le X, Y, Z, A, B, C\le 77$, $Q(1\le Q\le 77)$组询问,每次给$A, B, C, D$, 求上式的值。

Solution

$x, y, z$坐标都很小($1\le x, y, z\le 77$)，差的取值也很小，不妨构造多项式$A[N^2\times x + N\times y + z] += 1$, $B[N^2\times (77-x)+N\times (77 - y)+(77-z)]+=1$。令$N=77*2$
我们发现$A\times B=N^2\times (77+x[i]-x[j]) + N\times (77+y[i]-y[j]) + (77+z[i]-z[j])$
显然$x[i]-x[j],y[i]-y[j],z[i]-z[j]$我们可以通过，于是这题FFT一下就做完了= =

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int N = 153;
const double PI = acos(-1.0);
double D[80][80][80];
namespace FFT {
  static const int W = 1 << 22;
  static const double PI = acos(-1.0);
  struct Complex {
    double x, y;
    Complex(double _x = 0, double _y = 0) : x(_x), y(_y) {}
    Complex operator + (const Complex &t) const {return Complex(x + t.x, y + t.y);}
    Complex& operator += (const Complex &t) {x += t.x, y += t.y;return *this;}
    Complex operator - (const Complex &t) const {return Complex(x-t.x,y-t.y);}
    Complex& operator -= (const Complex &t) {x -= t.x, y -= t.y;return *this;}
    Complex operator * (const Complex &t) const {return Complex(x * t.x - y * t.y, x * t.y + y * t.x);}
    Complex operator / (const double &t) const {return Complex(x / t,y / t);}
    Complex& operator /= (const double &t) {x /= t, y /= t;return *this;}
    double real() {return x;}
    double imag() {return y;}
  };
  void fft(Complex a[], int n, int rev) {// rev=-1, reverse
      for (int i = 1, j = 0, k; i < n; ++i) {
          for (k = n >> 1; k > (j ^= k); k >>= 1);
          if (i < j) swap(a[i], a[j]);
      }
      for (int s = 1, ss = 2; s < n; s <<= 1,ss <<= 1) {
          Complex wn(cos(2 * PI * rev / ss), sin(2 * PI * rev / ss)), w;
          for (int i = 0, j ; i < n; i += ss) {
              for (j = i, w = 1; j < i + s; ++j, w = w * wn) {
                  Complex t = w * a[j + s];
                  a[j + s] = a[j] - t; 
                  a[j] = a[j] + t;
              }
          }
      }
      if (rev == -1) for (int i = 0; i < n; ++i) a[i] /= n;
  }
}
FFT::Complex A[FFT::W], B[FFT::W];
inline double sqrr(double x) {
    return x * x * x * x;
}
int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    for (int i = 1, x, y, z; i <= n; ++i) {
        scanf("%d%d%d", &x, &y, &z);
        --x, --y, --z;
        int t1 = N * N * x + N * y + z, t2 = N * N * (76 - x) + N * (76 - y) + (76 - z);
        A[t1].x += 1, B[t2].x += 1;
    }
    for (int i = 0; i <= 77; ++i)
        for (int j = 0; j <= 77; ++j)
            for (int k = 0; k <= 77; ++k)
                D[i][j][k] = sqrt(sqrr(i) + sqrr(j) + sqrr(k));
    FFT::fft(A, FFT::W, 1);
    FFT::fft(B, FFT::W, 1);
    for (int i = 0; i < FFT::W; ++i)    A[i] = A[i] * B[i];
    FFT::fft(A, FFT::W, -1);
    while (q--) {
        double ans = 0;
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        for (int i = 0; i < FFT::W; ++i) {
            int cnt = int(A[i].real() + 0.5);
            if (!cnt)   continue;
            int x = i / (N * N) - 76, y = i / N % N - 76, z = i % N - 76;
            if (!x && !y && !z) continue;
            ans += fabs(a * x + b * y + c * z + d) * cnt / D[abs(x)][abs(y)][abs(z)];
        }
        ans /= n, ans /= n - 1;
        printf("%.10lf\n", ans);
    }
    return 0;
}

总结

自己还是太年轻，一看范围小就想着想忽略近似计算和乱搞，犯了方向性的错误= =。。还是要多加思考QvQ