#26104 (C++11) No.206 数の積集合を求めるクエリ

• 問題: No.206 数の積集合を求めるクエリ
• ユーザー: Min_25
• 提出日時: 2015-05-11 03:26:59
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 50 ms / 7,000 ms
• コード長: 5,042 bytes
• コンパイル時間: 753 ms
• コンパイル使用メモリ: 82,320 KB
• 実行使用メモリ: 5,504 KB
• 最終ジャッジ日時: 2024-07-05 22:17:11
• 合計ジャッジ時間: 2,759 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	3 ms; 5,376 KB
testcase_09	AC	3 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	3 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB
testcase_15	AC	3 ms; 5,376 KB
testcase_16	AC	2 ms; 5,376 KB
testcase_17	AC	48 ms; 5,504 KB
testcase_18	AC	47 ms; 5,376 KB
testcase_19	AC	48 ms; 5,376 KB
testcase_20	AC	47 ms; 5,376 KB
testcase_21	AC	48 ms; 5,376 KB
testcase_22	AC	48 ms; 5,376 KB
testcase_23	AC	48 ms; 5,376 KB
testcase_24	AC	50 ms; 5,376 KB
testcase_25	AC	50 ms; 5,376 KB
testcase_26	AC	49 ms; 5,376 KB
testcase_27	AC	48 ms; 5,376 KB
testcase_28	AC	50 ms; 5,376 KB
testcase_29	AC	50 ms; 5,376 KB
testcase_30	AC	49 ms; 5,376 KB

ソースコード

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cassert>

#include <iostream>
#include <utility>
#include <algorithm>
#include <queue>
#include <functional>
#include <vector>
#include <map>
#include <set>

#define getchar getchar_unlocked
#define putchar putchar_unlocked

using namespace std;

typedef long long int64;
typedef long long unsigned uint64;
typedef long double float80;
typedef unsigned short uint16;
typedef unsigned uint;
typedef unsigned char uint8;

uint get_uint() {
  uint n;
  int c;
  while( (c = getchar()) < '0') {
    ;
  }
  n = c - '0';
  while( (c = getchar()) >= '0') {
    n = n * 10 + (c - '0');
  }
  return n;
}

void put_uint(uint n) {
  uint8 stack[30];
  int top = 0;
  do {
    stack[top++] = n % 10 + '0';
    n /= 10;
  } while(n != 0);
  while(top > 0) {
    putchar(stack[--top]);
  }
  putchar('\n');
}

template <uint mod, uint peri>
class Mod32 {
private:
  uint n_;

public:
  static const uint* roots;

  Mod32() {}
  Mod32(uint v) : n_(v) {}
  static Mod32 inv2(){ return (mod + 1) / 2; }
  static uint period() { return peri; }
  Mod32 operator+ (Mod32 rhs) const {
    uint ret = (this->n_ + rhs.n_);
    return Mod32(ret >= mod ? ret - mod : ret);
  }
  Mod32 operator- (Mod32 rhs) const {
    uint ret = (this->n_ - rhs.n_);
    return Mod32(int(ret) < 0 ? ret + mod : ret);
  }
  Mod32 operator* (Mod32 rhs) const {
    return Mod32(uint64(this->n_) * rhs.n_ % mod);
  }
  Mod32 operator+= (Mod32 rhs) {
    return *this = *this + rhs;
  }
  Mod32 operator-= (Mod32 rhs) {
    return *this = *this - rhs;
  }
  Mod32 operator*= (Mod32 rhs) {
    return *this = *this * rhs;
  }
  uint get_value() const {
    return this->n_;
  }
  void set_value(uint val) {
    this->n_ = val;
  }
  Mod32 inverse() const {
    return Mod32(pow_mod(n_, mod - 2));
  }
  static uint pow_mod(uint base, uint exp) {
    uint ret = 1;
    while(exp) {
      if(exp & 1) {
        ret = uint64(ret) * base % mod;
      }
      exp >>= 1;
      base = uint64(base) * base % mod;
    }
    return ret;
  }
};

const uint MOD = 469762049;
typedef Mod32<MOD, 26> mod32_t;

const uint roots32[] = {
  2187, 4782969, 320192759, 385303873, 391371999, 
  297449090, 197868229, 49553715, 422997289, 321129726, 
  386080322, 372627191, 19512135, 62025685, 244412522, 
  165447688, 110059487, 25153357, 338628632, 189158148, 
  210853138, 244709223, 426037461, 129701348, 450151958, 
  469762048, 1
};

template <>
const uint * mod32_t::roots = roots32;

// -----------------------------------------------------------------------------

template <typename T>
inline void sumdiff(T& a, T& b) {
  T t = a - b;
  a += b;
  b = t;
}

template <typename T>
void revbin_permute(T* A, uint n) {
  if(n <= 2)
    return;
  uint r = 0;
  uint nh = n >> 1;
  for(uint x = 1; x < n; ++x) {
    uint h = nh;
    while(! ((r ^= h) & h))
      h >>= 1;
    if(r > x)
      swap(A[x], A[r]);
  }
}

template <typename mod_t>
void ntt_dit4_core(mod_t *f, uint ldn, int sign) {
  const uint LX = 2;
  const uint n = 1u << ldn;
  
  if(ldn & 1) {
    for(uint i = 0; i < n; i += 2) {
      sumdiff(f[i], f[i+1]);
    }
  }

  mod_t imag = mod_t(mod_t::roots[mod_t::period() - 2]);
  if(sign < 0) {
    imag = imag.inverse();
  }

  uint ldm = LX + (ldn & 1);
  for(; ldm <= ldn; ldm += LX) {
    const uint m = 1u << ldm;
    const uint m4 = m >> LX;

    mod_t dw = mod_t(mod_t::roots[mod_t::period() - ldm]);
    if(sign < 0) {
      dw = dw.inverse();
    }
    mod_t w = mod_t(1);
    mod_t w2 = w;
    mod_t w3 = w;

    for(uint j = 0; j < m4; ++j) {
      for(uint r = 0, i0 = j + r; r < n; r += m, i0 += m) {
        const uint i1 = i0 + m4;
        const uint i2 = i1 + m4;
        const uint i3 = i2 + m4;

        mod_t a0 = f[i0];
        mod_t a2 = f[i1] * w2;
        mod_t a1 = f[i2] * w;
        mod_t a3 = f[i3] * w3;

        mod_t t02 = a0 + a2;
        mod_t t13 = a1 + a3;

        f[i0] = t02 + t13;
        f[i2] = t02 - t13;

        t02 = a0 - a2;
        t13 = a1 - a3;
        t13 *= imag;

        f[i1] = t02 + t13;
        f[i3] = t02 - t13;
      }

      w *= dw;
      w2 = w * w;
      w3 = w * w2;
    }
  }
}

template <typename mod_t>
void ntt_dit4(mod_t* f, uint ldn, int sign) {
  revbin_permute(f, 1u << ldn);
  ntt_dit4_core(f, ldn, sign);
}

mod32_t A[1 << 18];
mod32_t B[1 << 18];

void solve() {
  uint L = get_uint();
  uint M = get_uint();
  uint N = get_uint();

  uint ntt_size = 1;
  uint ldn = 0;
  while (ntt_size < N) {
    ntt_size <<= 1;
    ldn++;
  }
  ntt_size <<= 1;
  ++ldn;

  for (uint i = 0; i < L; ++i) {
    A[get_uint()] = 1;
  }
  ntt_dit4(A, ldn, 1);

  for (uint i = 0; i < M; ++i) {
    B[N - get_uint()] = 1;
  }
  ntt_dit4(B, ldn, 1);

  for (uint i = 0; i < ntt_size; ++i) {
    A[i] *= B[i];
  }
  ntt_dit4(A, ldn, -1);

  uint Q = get_uint();

  mod32_t inv = mod32_t(ntt_size).inverse();
  for (uint i = N; i < N + Q; ++i) {
    put_uint( (A[i] * inv).get_value() );
  }
}

int main() {
  solve();
  return 0;
}