結果

問題 No.206 数の積集合を求めるクエリ
ユーザー はまやんはまやん
提出日時 2017-05-20 11:20:42
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 136 ms / 7,000 ms
コード長 2,249 bytes
コンパイル時間 1,877 ms
コンパイル使用メモリ 174,292 KB
実行使用メモリ 20,808 KB
最終ジャッジ日時 2024-09-19 00:24:41
合計ジャッジ時間 6,061 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
const double PI = acos(-1.0);
typedef complex<double> P;
void fft(vector<P> &a, int isRev = 0) { // 配列aのサイズは2の累乗じゃないとダメ
    const P I(0.0, 1.0); int n = a.size(); double theta = 2 * PI / n; if (isRev) theta = -2 * PI / n;
    for (int m = n; m >= 2; m >>= 1) { int mh = m >> 1; rep(i, 0, mh) { P w = exp(i*theta*I);
    for (int j = i; j < n; j += m) { int k = j + mh; P x = a[j] - a[k]; a[j] += a[k]; a[k] = w * x; } }
        theta *= 2; } int i = 0;
    rep(j, 1, n - 1) { for (int k = n >> 1; k >(i ^= k); k >>= 1); if (j < i) swap(a[i], a[j]); }
    if (isRev) rep(i, 0, n) a[i] /= n; }
vector<int> convolution(vector<int> a, vector<int> b) {
    int n = a.size(), m = 1; while (m < n) m *= 2;
    vector<P> A(m), B(m); rep(i, 0, n) { A[i] = P(a[i], 0); B[i] = P(b[i], 0); } fft(A); fft(B);
    vector<P> C(m); rep(i, 0, m) C[i] = A[i] * B[i]; fft(C, 1);
    vector<int> res; rep(i, 0, n) res.push_back(int(real(C[i]) + 0.3)); return res; }
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/




int L, M, N, A[101010], B[101010], Q;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> L >> M >> N;
    rep(i, 0, L) cin >> A[i];
    rep(i, 0, M) cin >> B[i];
    cin >> Q;

    vector<int> a(N * 2 + 2), b(N * 2 + 2);
    rep(i, 0, L) a[A[i]] = 1;
    rep(i, 0, M) b[N - B[i]] = 1;

    auto ans = convolution(a, b);
    rep(i, N, N + Q) printf("%d\n", ans[i]);
}
0