結果

問題 No.206 数の積集合を求めるクエリ
コンテスト
ユーザー kazuma
提出日時 2018-03-25 10:03:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 378 ms / 7,000 ms
コード長 2,065 bytes
コンパイル時間 2,378 ms
コンパイル使用メモリ 201,828 KB
最終ジャッジ日時 2025-01-05 09:34:32
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const double pi = acos(-1);

typedef complex<double> Comp;

int size(int n) {
	int res = 1;
	while (res < n) res <<= 1;
	return res;
}

void fft(vector<Comp>& v) {
	int n = size(v.size());
	if (n >(int)v.size()) v.resize(n);
	for (int j = 1, i = 0; j < n - 1; j++) {
		for (int k = n >> 1; k >(i ^= k); k >>= 1);
		if (j < i) swap(v[i], v[j]);
	}
	for (int m = 2; m <= n; m <<= 1) {
		double deg = (-1) * 2 * pi / m;
		Comp r(cos(deg), sin(deg));
		for (int i = 0; i < n; i += m) {
			Comp w(1, 0);
			for (int j = i, k = i + m / 2; k < i + m; j++, k++) {
				Comp t1 = v[j], t2 = w * v[k];
				v[j] = t1 + t2, v[k] = t1 - t2;
				w *= r;
			}
		}
	}
}

void ifft(vector<Comp>& v) {
	int n = size(v.size());
	if (n > (int)v.size()) v.resize(n);
	for (int j = 1, i = 0; j < n - 1; j++) {
		for (int k = n >> 1; k >(i ^= k); k >>= 1);
		if (j < i) swap(v[i], v[j]);
	}
	for (int m = 2; m <= n; m <<= 1) {
		double deg = 2 * pi / m;
		Comp r(cos(deg), sin(deg));
		for (int i = 0; i < n; i += m) {
			Comp w(1, 0);
			for (int j = i, k = i + m / 2; k < i + m; j++, k++) {
				Comp t1 = v[j], t2 = w * v[k];
				v[j] = t1 + t2, v[k] = t1 - t2;
				w *= r;
			}
		}
	}
	for (int i = 0; i < n; ++i) v[i] *= 1.0 / n;
}

vector<int> convolution(const vector<int>& p, const vector<int>& q) {
	int n = size(p.size() + q.size());
	vector<Comp> P(n), Q(n);
	for (int i = 0; i < (int)p.size(); i++) P[i] = p[i];
	for (int i = 0; i < (int)q.size(); i++) Q[i] = q[i];
	fft(P); fft(Q);
	for (int i = 0; i < n; i++) P[i] *= Q[i];
	ifft(P);
	vector<int> res(n);
	for (int i = 0; i < n; i++) {
		res[i] = round(P[i].real());
	}
	return res;
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int L, M, N, Q;
	cin >> L >> M >> N;
	vector<int> cnt1(N + 1), cnt2(N + 1);
	for (int i = 0; i < L; i++) {
		int A;
		cin >> A;
		cnt1[A]++;
	}
	for (int i = 0; i < M; i++) {
		int B;
		cin >> B;
		cnt2[N - B]++;
	}
	auto v = convolution(cnt1, cnt2);
	cin >> Q;
	for (int i = 0; i < Q; i++) {
		cout << v[N + i] << endl;
	}
	return 0;
}
0