結果

問題 No.206 数の積集合を求めるクエリ
ユーザー iwiwiiwiwi
提出日時 2015-05-10 22:17:49
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 104 ms / 7,000 ms
コード長 3,813 bytes
コンパイル時間 979 ms
コンパイル使用メモリ 83,200 KB
実行使用メモリ 9,676 KB
最終ジャッジ日時 2023-09-20 01:45:58
合計ジャッジ時間 3,922 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 3 ms
4,380 KB
testcase_07 AC 3 ms
4,376 KB
testcase_08 AC 3 ms
4,384 KB
testcase_09 AC 3 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 3 ms
4,376 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 3 ms
4,380 KB
testcase_15 AC 3 ms
4,380 KB
testcase_16 AC 3 ms
4,380 KB
testcase_17 AC 96 ms
9,348 KB
testcase_18 AC 86 ms
9,516 KB
testcase_19 AC 94 ms
9,344 KB
testcase_20 AC 84 ms
9,676 KB
testcase_21 AC 86 ms
9,480 KB
testcase_22 AC 86 ms
9,476 KB
testcase_23 AC 94 ms
9,520 KB
testcase_24 AC 104 ms
9,400 KB
testcase_25 AC 102 ms
9,512 KB
testcase_26 AC 92 ms
9,544 KB
testcase_27 AC 87 ms
9,480 KB
testcase_28 AC 94 ms
9,544 KB
testcase_29 AC 94 ms
9,672 KB
testcase_30 AC 90 ms
9,412 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
using namespace std;

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)

typedef long long ll;


inline ll mod_pow(ll a, ll k, ll m) {
  ll r = 1;
  for (; k > 0; k >>= 1) {
    if (k & 1) (r *= a) %= m;
    (a *= a) %= m;
  }
  return r;
}

inline ll mod_inv(ll a, ll m) {
  ll b = m, u = 1, v = 0;
  while (b) {
    ll t = a / b;
    swap(a -= t * b, b);
    swap(u -= t * v, v);
  }
  return (u % m + m) % m;
}

// http://math314.hateblo.jp/entry/2015/05/07/014908
template<int Mod, int PrimitiveRoot>
class number_theoretic_transform {
 public:
  static void transform_forward(vector<ll> &a) {
    transform<1>(a);
  }

  static void transform_inverse(vector<ll> &a) {
    transform<-1>(a);
    const ll inv_n = mod_inv(a.size(), Mod);
    for (auto &x : a) (x *= inv_n) %= Mod;
  }

  static vector<ll> convolution(vector<ll> a, vector<ll> b) {
    size_t n = 1;
    while (n < a.size() + b.size()) n *= 2;
    a.resize(n);
    b.resize(n);

    transform_forward(a);
    transform_forward(b);
    for (size_t i = 0; i < n; ++i) (a[i] *= b[i]) %= Mod;
    transform_inverse(a);
    return a;
  }

 private:
  template<int Sign>
  static void transform(vector<ll> &a) {
    const size_t n = a.size();
    assert((n ^ (n & -n)) == 0);  // n = 2^k

    const ll h = Sign == 1 ?
        mod_pow(PrimitiveRoot, (Mod - 1) / n, Mod):
        mod_inv(mod_pow(PrimitiveRoot, (Mod - 1) / n, Mod), Mod);

    for (size_t i = 0, j = 0; j < n; ++j) {
      if (j < i) swap(a[i], a[j]);
      for (size_t k = n >> 1; k > (i ^= k); k >>= 1);
    }

    for (size_t m = 1; m < n; m *= 2) {
      const size_t m2 = m * 2;
      const ll b = mod_pow(h, n / m2, Mod);
      ll w = 1;
      for (size_t j = 0; j < m; ++j) {
        for (size_t k = j; k < n; k += m2) {
          const ll x = a[k];
          const ll y = (a[k + m] * w) % Mod;
          const ll tx = x + y;
          const ll ty = x - y;
          a[k] = tx >= Mod ? tx - Mod : tx;
          a[k + m] = ty < 0 ? ty + Mod : ty;
        }
        (w *= b) %= Mod;
      }
    }
  }
};

/*
vector<ll> mod_convolution(vector<ll> a, vector<ll> b, ll mod) {
  constexpr ll m1 = 167772161;
  constexpr ll m2 = 469762049;
  constexpr ll m3 = 1224736769;

  auto c1 = number_theoretic_transform<m1, 3>::convolution(a, b);
  const auto c2 = number_theoretic_transform<m2, 3>::convolution(a, b);
  const auto c3 = number_theoretic_transform<m3, 3>::convolution(a, b);

  const ll m1_inv_m2 = mod_inv(m1, m2);
  const ll m12_inv_m3 = mod_inv(m1 * m2, m3);
  const ll m12_mod = m1 * m2 % mod;
  for (size_t i = 0; i < c1.size(); ++i) {
    const ll v1 = (c2[i] - c1[i] + m2) * m1_inv_m2 % m2;
    const ll v2 = (c3[i] - (c1[i] + m1 * v1) % m3 + m3) * m12_inv_m3 % m3;
    c1[i] = (c1[i] + m1 * v1 + m12_mod * v2) % mod;
  }
  return c1;
}
*/

int main() {
  int AN, BN, K;
  while (3 == scanf("%d%d%d", &AN, &BN, &K)) {
    vector<long long> A(K), B(K);
    rep (i, AN) {
      int a;
      scanf("%d", &a);
      --a;
      A[K - 1 - a] = 1;
    }

    rep (i, BN) {
      int b;
      scanf("%d", &b);
      --b;
      B[b] = 1;
    }

    vector<long long> C = number_theoretic_transform<167772161, 3>::convolution(A, B);

    int Q;
    scanf("%d", &Q);
    rep (i, Q) {
      printf("%d\n", (int)C[K - 1 - i]);
    }
  }

  return 0;
}
0