結果

問題 No.206 数の積集合を求めるクエリ
コンテスト
ユーザー akakimidori
提出日時 2019-04-27 02:36:35
言語 C
(gcc 13.3.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,586 bytes
コンパイル時間 328 ms
コンパイル使用メモリ 34,432 KB
実行使用メモリ 15,104 KB
最終ジャッジ日時 2024-11-26 03:15:23
合計ジャッジ時間 8,969 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14 RE * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>
#include<math.h>

typedef int32_t i32;

typedef struct complex {
  double re;
  double im;
} complex;

typedef complex fft_val;

static inline fft_val fft_val_add (const fft_val a, const fft_val b) {
  return (complex) {a.re + b.re, a.im + b.im};
}

static inline fft_val fft_val_mul (const fft_val a, const fft_val b) {
  return (complex) {a.re * b.re - a.im * b.im, a.re * b.im + a.im * b.re};
}

void fft (const fft_val r, fft_val *f, const uint32_t n, fft_val *g) {
  if (n == 1) {
    g[0] = f[0];
    return;
  }
  const uint32_t m = n / 2;
  for (uint32_t i = 0; i < m; ++i) {
    g[i] = f[2 * i];
    g[i + m] = f[2 * i + 1];
  }
  const fft_val r2 = fft_val_mul (r, r);
  fft (r2, g, m, f);
  fft (r2, g + m, m, f + m);
  g[0] = fft_val_add (f[0], f[m]);
  fft_val q = r;
  for (uint32_t i = 1; i < m; ++i, q = fft_val_mul (q, r)) {
    g[i] = fft_val_add (f[i], fft_val_mul (q, f[i + m]));
  }
  for (uint32_t i = m; i < n; ++i, q = fft_val_mul (q, r)) {
    g[i] = fft_val_add (f[i - m], fft_val_mul (q, f[i]));
  }
}

void multiply (i32 *c, i32 *a, i32 *b, uint32_t n) {
  uint32_t k = 1;
  while (k < 2 * n - 1) k *= 2;
  fft_val *f = (fft_val *) calloc (k, sizeof (fft_val));
  fft_val *g = (fft_val *) calloc (k, sizeof (fft_val));
  fft_val *tmp = (fft_val *) calloc (k, sizeof (fft_val));
  for (uint32_t i = 0; i < k; ++i) {
    if (i < n) {
      tmp[i] = (complex) {a[i], 0};
    } else {
      tmp[i] = (complex) {0, 0};
    }
  }
  const double pi = 3.141592653589793;
  complex r = (complex) {cos (2 * pi / k), sin (2 * pi / k)}; 
  fft (r, tmp, k, f);
  for (uint32_t i = 0; i < k; ++i) {
    if (i < n) {
      tmp[i] = (complex) {b[i], 0};
    } else {
      tmp[i] = (complex) {0, 0};
    }
  }
  fft (r, tmp, k, g);
  for (uint32_t i = 0; i < k; ++i) {
    f[i] = fft_val_mul (f[i], g[i]);
  }
  r.im *= -1;//inv
  fft (r, f, k, g);
  for (uint32_t i = 0; i < 2 * n - 1; ++i) {
    c[i] = (i32)(g[i].re / k + 0.5);
  }
  free (f);
  free (g);
  free (tmp);
}

void run (void) {
  i32 l, m, n;
  scanf ("%" SCNi32 "%" SCNi32 "%" SCNi32, &l, &m, &n);
  i32 *a = (i32 *) calloc (n + 1, sizeof (i32));
  i32 *b = (i32 *) calloc (n + 1, sizeof (i32));
  while (l--) {
    i32 v;
    scanf ("%" SCNi32, &v);
    a[v] = 1;
  }
  while (m--) {
    i32 v;
    scanf ("%" SCNi32, &v);
    b[n - v] = 1;
  }
  multiply (a, a, b, n + 1);
  i32 q;
  scanf ("%" SCNi32, &q);
  for (i32 i = 0; i < q; ++i) {
    printf ("%" PRIi32 "\n", a[i + n]);
  }
}

int main (void) {
  run();
  return 0;
}
0