結果

問題 No.206 数の積集合を求めるクエリ
コンテスト
ユーザー lumc_
提出日時 2018-03-21 21:15:54
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 646 ms / 7,000 ms
コード長 2,684 bytes
コンパイル時間 2,007 ms
コンパイル使用メモリ 167,144 KB
実行使用メモリ 19,208 KB
最終ジャッジ日時 2024-06-24 19:41:06
合計ジャッジ時間 11,540 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll extgcd(ll a, ll b, ll &x, ll &y) {
  if(b == 0) {
    x = 1, y = 0;
    return a;
  }
  ll d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}

ll modinv(ll a, ll mod) {
  a = (a % mod + mod) % mod;
  ll x = 0, y = 0;
  extgcd(a, mod, x, y);
  return (x % mod + mod) % mod;
}

ll modpow(ll a, ll b, ll mod) {
  a = (a % mod + mod) % mod;
  ll r = 1;
  while(b) {
    if(b & 1) r = r * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return r;
}

template<ll mod>
struct ModInt {
  ll val;
  ModInt(): val(0) {}
  ModInt(ll v): val((v % mod + mod) % mod) {}
  ModInt operator+(ModInt rhs) {
    return ModInt<mod>(val + rhs.val);
  }
  ModInt operator*(ModInt rhs) {
    return ModInt<mod>(val * rhs.val);
  }
  ModInt operator/(ModInt rhs) {
    return ModInt<mod>(val * rhs.inv().val);
  }
  ModInt operator+=(ModInt rhs) {
    val = (val + rhs.val) % mod;
    return *this;
  }
  ModInt operator*=(ModInt rhs) {
    val = (val * rhs.val) % mod;
    return *this;
  }
  ModInt operator/=(ModInt rhs) {
    val = (val * rhs.inv().val) % mod;
    return *this;
  }
  ModInt inv() {
    return ModInt<mod>(modinv(val, mod));
  }
};

template<ll mod, ll primitive>
struct NTT {
  const int Mod = mod;
  using Int = ModInt<mod>;
  vector<Int> fft(vector<Int> a, bool inv = 0) {
    int n = a.size(), n2 = n / 2;
    if(n == 1) return a;
    vector<Int> a0(n2), a1(n2);
    for(int i = 0; i < n2; i++) a0[i] = a[i * 2], a1[i] = a[i * 2 + 1];
    a0 = fft(a0); a1 = fft(a1);
    Int zeta(modpow(primitive, (mod - 1) / n, mod));
    if(inv) zeta = zeta.inv();
    Int tmp(1);
    for(int i = 0; i < n; i++) {
      int ii = i;
      if(inv) ii = n - i;
      a[i] = a0[ii % n2] + tmp * a1[ii % n2];
      if(inv) a[i] /= Int(n);
      tmp *= zeta;
    }
    return a;
  }
  template<typename T>
  vector<Int> conv(vector<T> at, vector<T> bt) {
    int deg = at.size() + bt.size();
    int n = 1;
    while(n < deg) n <<= 1;
    vector<Int> a(n), b(n);
    for(int i = 0; i < (int) at.size(); i++) a[i] = Int(at[i]);
    for(int i = 0; i < (int) bt.size(); i++) b[i] = Int(bt[i]);
    a = fft(a); b = fft(b);
    vector<Int> c(n);
    for(int i = 0; i < n; i++) c[i] = a[i] * b[i];
    return fft(c, 1);
  }
};

NTT<(1 << 25) * 5 + 1, 3> ntt;

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int l, m , n; cin >> l >> m >> n;
  vector<int> a(n + 1), b(n + 1);
  for(int i = 0; i < l; i++) { int x; cin >> x; a[x] = 1; }
  for(int i = 0; i < m; i++) { int x; cin >> x; b[n - x] = 1; }
  auto c = ntt.conv(a, b);
  int q; cin >> q;
  for(int i = n; i < n + q; i++) {
    cout << c[i].val << endl;
  }
}
0