結果

問題 No.206 数の積集合を求めるクエリ
ユーザー Min_25Min_25
提出日時 2015-05-11 03:35:07
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 51 ms / 7,000 ms
コード長 5,014 bytes
コンパイル時間 707 ms
コンパイル使用メモリ 82,572 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 22:17:50
合計ジャッジ時間 2,702 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 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 3 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 3 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 3 ms
5,376 KB
testcase_16 AC 3 ms
5,376 KB
testcase_17 AC 48 ms
5,376 KB
testcase_18 AC 47 ms
5,376 KB
testcase_19 AC 49 ms
5,376 KB
testcase_20 AC 46 ms
5,376 KB
testcase_21 AC 47 ms
5,376 KB
testcase_22 AC 48 ms
5,376 KB
testcase_23 AC 48 ms
5,376 KB
testcase_24 AC 51 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 51 ms
5,376 KB
testcase_30 AC 49 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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) {
        mod_t a0 = f[i0 + m4 * 0];
        mod_t a2 = f[i0 + m4 * 1] * w2;
        mod_t a1 = f[i0 + m4 * 2] * w;
        mod_t a3 = f[i0 + m4 * 3] * w3;

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

        f[i0 + m4 * 0] = t02 + t13;
        f[i0 + m4 * 2] = t02 - t13;

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

        f[i0 + m4 * 1] = t02 + t13;
        f[i0 + m4 * 3] = 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;
}
0