結果

問題 No.206 数の積集合を求めるクエリ
コンテスト
ユーザー 0x19f
提出日時 2018-06-26 03:40:43
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 465 ms / 7,000 ms
コード長 2,033 bytes
コンパイル時間 1,408 ms
コンパイル使用メモリ 168,712 KB
実行使用メモリ 51,732 KB
最終ジャッジ日時 2024-06-30 22:51:42
合計ジャッジ時間 8,029 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;

const double pi = acos(-1);

vector<complex<double>> fft(vector<complex<double>> f, int n, int sign) {
  if(n == 1) return f;

  vector<complex<double>> f0(n / 2), f1(n / 2);
  for(int i = 0; i < n / 2; i++) {
    f0[i] = f[i * 2];
    f1[i] = f[i * 2 + 1];
  }

  vector<complex<double>> ft0 = fft(f0, n / 2, sign);
  vector<complex<double>> ft1 = fft(f1, n / 2, sign);

  vector<complex<double>> ft(n);
  complex<double> zeta(cos(2 * pi / n), sign * sin(2 * pi / n));
  complex<double> x = 1;
  for(int i = 0; i < n / 2; i++) {
    ft[i] = ft0[i] + x * ft1[i];
    x *= zeta;
  }
  for(int i = 0; i < n / 2; i++) {
    ft[n / 2 + i] = ft0[i] + x * ft1[i];
    x *= zeta;
  }

  return ft;
}

vector<complex<double>> dft(vector<complex<double>> f) {
  int n = f.size();
  vector<complex<double>> ft = fft(f, n, 1);
  return ft;
}

vector<complex<double>> idft(vector<complex<double>> ft) {
  int n = ft.size();
  vector<complex<double>> f = fft(ft, n, -1);
  for(int i = 0; i < n; i++) f[i] /= n;
  return f;
}

vector<double> convolution(vector<double> a, vector<double> b) {
  ll p = a.size(), q = b.size();
  ll n = 1;
  while(n < p + q + 1) n *= 2;

  vector<complex<double>> g(n), h(n);
  for(int i = 0; i < p; i++) g[i] = a[i];
  for(int i = 0; i < q; i++) h[i] = b[i];

  vector<complex<double>> gt = dft(g);
  vector<complex<double>> ht = dft(h);

  vector<complex<double>> ft(n);
  for(int i = 0; i < n; i++) ft[i] = gt[i] * ht[i];

  vector<complex<double>> f = idft(ft);

  vector<double> c(n);
  for(int i = 0; i < n; i++) c[i] = f[i].real();
  return c;
}

int main(void) {
  ll L, M, N;
  cin >> L >> M >> N;
  vector<double> A(N + 1), B(N + 1);
  REP(i, 0, L) {
    ll a;
    cin >> a;
    A[a] = 1;
  }
  REP(i, 0, M) {
    ll b;
    cin >> b;
    B[N - b] = 1;
  }
  ll Q;
  cin >> Q;

  vector<double> ans = convolution(A, B);
  REP(i, 0, Q) cout << (ll) (ans[N + i] + 0.5) << endl;
}
0