結果

問題 No.206 数の積集合を求めるクエリ
コンテスト
ユーザー rogi52
提出日時 2021-08-14 22:04:10
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 862 ms / 7,000 ms
コード長 1,983 bytes
コンパイル時間 1,735 ms
コンパイル使用メモリ 178,360 KB
実行使用メモリ 43,612 KB
最終ジャッジ日時 2024-10-05 22:33:48
合計ジャッジ時間 15,715 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

vector<complex<double>> fft(vector<complex<double>> f, int inv = 0){
    int n = f.size();
    if(n == 1) return f;
    vector<complex<double>> f_e, f_o;
    for(int i = 0; i < n; i++){
        if(i % 2 == 0) f_e.push_back(f[i]); else f_o.push_back(f[i]);
    }
    vector<complex<double>> F_e = fft(f_e, inv), F_o = fft(f_o, inv);
    vector<complex<double>> ret;
    for(int i = 0; i < n; i++){
        complex<double> zeta = exp(i * 2 * M_PI / (double)n * complex<double>{0, 1.0} * (double)(inv ? -1 : +1));
        int j = i % (n / 2);
        ret.push_back(F_e[j] + zeta * F_o[j]);
    }
    return ret;
}

vector<complex<double>> change(vector<complex<double>> f){
    int n = 1;
    while(n < f.size()) n <<= 1;
    while(f.size() < n) f.push_back(complex<double>{0, 0});
    return f;
}

template<class T>
vector<T> convolution(vector<T> a, vector<T> b){
    int N = a.size();
    vector<complex<double>> A, B;
    for(int i = 0; i < N; i++){
        A.push_back(complex<double>{(double)a[i], 0});
        B.push_back(complex<double>{(double)b[i], 0});
    }
    for(int i = 0; i < N; i++){
        A.push_back(complex<double>{0, 0});
        B.push_back(complex<double>{0, 0});
    }

    A = change(A);
    B = change(B);
    A = fft(A);
    B = fft(B);
    vector<complex<double>> C;
    for(int i = 0; i < A.size(); i++) C.push_back(A[i] * B[i]);
    C = fft(C, 1);
    vector<T> c;
    c.push_back(0);
    for(int i = 0; i < 2 * N - 1; i++){
        c.push_back((T)(C[i].real() / (double)C.size() + 0.5));
    }
    return c;
}


int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);

    int L,M,N; cin >> L >> M >> N;
    vector<int> A(N),B(N);
    rep(i,L){ int a; cin >> a; A[a - 1] = 1; }
    rep(i,M){ int b; cin >> b; B[N - 1 - (b - 1)] = 1; }

    vector<int> C = convolution(A, B);
    int Q; cin >> Q;
    rep(i,Q) printf("%d\n", C[N + i]);
}
0