結果

問題 No.206 数の積集合を求めるクエリ
ユーザー yuppe19 😺yuppe19 😺
提出日時 2016-07-07 18:42:41
言語 C++11
(gcc 11.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,426 bytes
コンパイル時間 448 ms
コンパイル使用メモリ 52,620 KB
最終ジャッジ日時 2024-11-14 19:46:29
合計ジャッジ時間 1,033 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:7:30: error: ‘vector’ has not been declared
    7 |   static void fmt(const int, vector<i64>&);
      |                              ^~~~~~
main.cpp:7:36: error: expected ‘,’ or ‘...’ before ‘<’ token
    7 |   static void fmt(const int, vector<i64>&);
      |                                    ^
main.cpp:8:31: error: ‘vector’ has not been declared
    8 |   static void ifmt(const int, vector<i64>&);
      |                               ^~~~~~
main.cpp:8:37: error: expected ‘,’ or ‘...’ before ‘<’ token
    8 |   static void ifmt(const int, vector<i64>&);
      |                                     ^
main.cpp:9:33: error: ‘vector’ has not been declared
    9 |   static void convol(const int, vector<i64>&, vector<i64>&);
      |                                 ^~~~~~
main.cpp:9:39: error: expected ‘,’ or ‘...’ before ‘<’ token
    9 |   static void convol(const int, vector<i64>&, vector<i64>&);
      |                                       ^
main.cpp:14:32: error: ‘vector’ has not been declared
   14 |   static void myfmt(const int, vector<i64>&, const bool);
      |                                ^~~~~~
main.cpp:14:38: error: expected ‘,’ or ‘...’ before ‘<’ token
   14 |   static void myfmt(const int, vector<i64>&, const bool);
      |                                      ^
main.cpp:17:53: error: return type ‘class std::tuple<long long int, long long int, long long int>’ is incomplete
   17 | tuple<i64, i64, i64> extgcd(const i64 x, const i64 y) {
      |                                                     ^
main.cpp: In function ‘void extgcd(i64, i64)’:
main.cpp:18:23: error: ‘make_tuple’ was not declared in this scope
   18 |   if(y == 0) { return make_tuple(1LL, 0LL, x); }
      |                       ^~~~~~~~~~
main.cpp:3:1: note: ‘std::make_tuple’ is defined in header ‘<tuple>’; did you forget to ‘#include <tuple>’?
    2 | #include <algorithm>
  +++ |+#include <

ソースコード

diff # 

#include <iostream>
#include <algorithm>
using namespace std;
using i64 = long long;

struct FMT {
  static void fmt(const int, vector<i64>&);
  static void ifmt(const int, vector<i64>&);
  static void convol(const int, vector<i64>&, vector<i64>&);
private:
  static constexpr i64 O = 3LL;
  static constexpr i64 M = 1224736769LL;
  static constexpr i64 N = M - 1;
  static void myfmt(const int, vector<i64>&, const bool);
};

tuple<i64, i64, i64> extgcd(const i64 x, const i64 y) {
  if(y == 0) { return make_tuple(1LL, 0LL, x); }
  i64 a, b, d; tie(a, b, d) = extgcd(y, x%y);
  return make_tuple(b, a-x/y*b, d);
}

i64 mod_inv(const i64 a, const i64 m) {
  i64 x, _, d; tie(x, _, d) = extgcd(a, m);
  return (x % m + m) % m;
}

i64 mod_pow(const i64 a, const i64 r, const i64 n, const i64 m) {
  if(n == 0) { return r; }
  if(n & 1)  { return mod_pow(a, a*r%m, n-1, m); }
  return mod_pow(a*a%m, r, n>>1, m);
}

i64 mod_pow(const i64 a, const i64 n, const i64 m) {
  return mod_pow(a, 1, n, m);
}

void FMT::myfmt(const int logn, vector<i64> &a, const bool inv) {
  const int n = 1 << logn;
  for(int H=1, W=n>>1; H<n; H<<=1, W>>=1) {
    vector<i64> y = a;
    i64 r = mod_pow(O, N/(H*2), M);
    if(inv) { r = mod_inv(r, M); }
    i64 w = 1;
    for(int k=0; k<H; ++k) {
      for(int j=0; j<W; ++j) {
        i64 y0 = y[2*W*k+j],
            y1 = y[2*W*k+j+W] * w % M;
        a[W* k   +j] = y0 + y1 < M ? y0 + y1     : y0 + y1 - M;
        a[W*(k+H)+j] = y0 < y1     ? y0 - y1 + M : y0 - y1;
      }
      w = w * r % M;
    }
  }
}

void FMT::fmt(const int logn, vector<i64> &a) {
  myfmt(logn, a, false);
}

void FMT::ifmt(const int logn, vector<i64> &a) {
  myfmt(logn, a, true);
  int n = 1 << logn;
  i64 inv = mod_inv(n, M);
  for(int i=0; i<n; ++i) {
    a[i] = a[i] * inv % M;
  }
}

void FMT::convol(const int logn, vector<i64> &a, vector<i64> &b) {
  fmt(logn, a);
  fmt(logn, b);
  for(int i=0; i<1<<logn; ++i) {
    a[i] = a[i] * b[i] % M;
  }
  ifmt(logn, a);
}

int main(void) {
  cin.tie(0); ios::sync_with_stdio(false);
  int L, M, N, Q; cin >> L >> M >> N;
  int size = (N + 1) * 2;
  int m; for(m=0; 1<<m <= 2*size; ++m) /* nop */ ;
  vector<i64> p(1<<m, 0), q(1<<m, 0);
  for(int i=0; i<L; ++i) { int x; cin >> x; p[x]   = true; }
  for(int i=0; i<M; ++i) { int x; cin >> x; q[N-x] = true; }
  FMT::convol(m, p, q);
  cin >> Q;
  for(int v=0; v<Q; ++v) {
    cout << p[N+v] << '\n';
  }
  return 0;
}
0