結果

問題 No.206 数の積集合を求めるクエリ
コンテスト
ユーザー koba-e964
提出日時 2015-06-11 15:09:27
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 217 ms / 7,000 ms
コード長 2,687 bytes
コンパイル時間 1,032 ms
コンパイル使用メモリ 82,004 KB
実行使用メモリ 19,796 KB
最終ジャッジ日時 2024-07-06 15:37:13
合計ジャッジ時間 4,101 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <complex>

/*
 * Fast fourier transformation. n must be a power of 2.
 * header requirement: vector, complex
 */
class FFT {
private:
  typedef std::complex<double> comp;
  static void
  inplace_internal_fft(
		       comp const *f,
		       comp *output,
		       comp const *ztbl,
		       int x,
		       int fstart,
		       int fstep,
		       int n,
		       int ostart) {
    if (n == 1) {
      output[ostart] = f[fstart];
      return;
    }
    inplace_internal_fft(f, output, ztbl, x + 1,
			 fstart, 2 * fstep, n / 2, ostart);
    inplace_internal_fft(f, output, ztbl, x + 1,
			 fstart + fstep, 2 * fstep, n / 2, ostart + n / 2);
    comp zeta = ztbl[x];
    comp pzeta = 1;
    for (int i = 0; i < n / 2; ++i) {
      comp f0 = output[ostart + i];
      comp f1 = output[ostart + i + n / 2];
      output[ostart + i] = f0 + pzeta * f1;
      output[ostart + i + n / 2] = f0 - pzeta * f1;
      pzeta *= zeta;
    }
    return;
  }
public:
  static int ceil_pow2(int n) {
    while (n & (n -1)) {
      n += n & (-n);
    }
    return n;
  }
  static std::vector<comp> transform(std::vector<comp> f, int n) {
    const double pi = 3.141592653589793238463;
    int p = __builtin_popcount(n - 1); // n = 2^p
    std::vector<comp> ztbl(p);
    for (int i = 0; i < p; ++i) {
      int d = n >> i;
      comp zeta = comp(cos(2 * pi / d), sin(2 * pi / d));
      ztbl[i] = zeta;
    }
    std::vector<comp> output(n);
    inplace_internal_fft(&f[0], &output[0], &ztbl[0], 0, 0, 1, n, 0);
    return output;
  }

  static std::vector<comp> inverse_transform(std::vector<comp> f, int n) {
    const double pi = 3.141592653589793238463;
    int p = __builtin_popcount(n - 1); // n = 2^p
    std::vector<comp> ztbl(p);
    for (int i = 0; i < p; ++i) {
      int d = n >> i;
      comp zeta = comp(cos(2 * pi / d), - sin(2 * pi / d));
      ztbl[i] = zeta;
    }
    std::vector<comp> output(n);
    inplace_internal_fft(&f[0], &output[0], &ztbl[0], 0, 0, 1, n, 0);
    for (int i = 0; i < n; i++) {
      output[i] /= n;
    }
    return output;
  }
};

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;

typedef complex<double> comp;
int main(void) {
  int l, m, n;
  cin >> l >> m >> n;
  n = FFT::ceil_pow2(n) * 2;
  vector<comp> a(n), b(n);
  REP(i, 0, l) {
    int t;
    cin >> t;
    a[t - 1] = 1;
  }
  REP(i, 0, m) {
    int t;
    cin >> t;
    b[n / 2 - t] = 1;
  }
  a = FFT::transform(a, n);
  b = FFT::transform(b, n);
  REP(i, 0, n) {
    a[i] *= b[i];
  }
  a = FFT::inverse_transform(a, n);
  int q;
  cin >> q;
  REP(i, 0, q) {
    cout << (int)(a[n / 2 - 1 + i].real() + 0.5) << endl;
  }
}
0