結果

問題 No.206 数の積集合を求めるクエリ
コンテスト
ユーザー yuppe19 😺
提出日時 2016-07-04 16:17:55
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,482 bytes
コンパイル時間 539 ms
コンパイル使用メモリ 51,524 KB
最終ジャッジ日時 2024-11-14 19:46:18
合計ジャッジ時間 1,241 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、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:13:32: error: ‘vector’ has not been declared
   13 |   static void myfmt(const int, vector<i64>&, const bool);
      |                                ^~~~~~
main.cpp:13:38: error: expected ‘,’ or ‘...’ before ‘<’ token
   13 |   static void myfmt(const int, vector<i64>&, const bool);
      |                                      ^
main.cpp:16:53: error: return type ‘class std::tuple<long long int, long long int, long long int>’ is incomplete
   16 | tuple<i64, i64, i64> extgcd(const i64 x, const i64 y) {
      |                                                     ^
main.cpp: In function ‘void extgcd(i64, i64)’:
main.cpp:17:23: error: ‘make_tuple’ was not declared in this scope
   17 |   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 W = 3LL;
  static constexpr i64 M = 1224736769LL;
  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) {
  int n = 1 << logn;
  i64 base = mod_pow(W, (M-1) / n, M);
  if(inv) { base = mod_inv(base, M); }
  for(int m=n; m>=2; m>>=1, base=base*base%M) {
    i64 w = 1;
    for(int i=0, mh=m>>1; i<mh; ++i, w=w*base%M) {
      for(int j=i; j<n; j+=m) {
        int k = j + mh;
        i64 x = a[j] < a[k] ? a[j] - a[k] + M : a[j] - a[k];
        a[j] = a[j] + a[k] < M ? a[j] + a[k] : a[j] + a[k] - M;
        a[k] = w * x % M;
      }
    }
  }
  for(int i=0, j=1; j<n-1; ++j) {
    for(int k=n>>1; k>(i^=k); k>>=1) /* nop */ ;
    if(j > i) { swap(a[i], a[j]); }
  }
}

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