結果
問題 | No.206 数の積集合を求めるクエリ |
ユーザー |
![]() |
提出日時 | 2020-08-02 05:03:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,794 bytes |
コンパイル時間 | 3,087 ms |
コンパイル使用メモリ | 208,368 KB |
最終ジャッジ日時 | 2025-01-12 13:07:04 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 WA * 11 RE * 2 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> p_ll; template<class T> void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; } #define repr(i,from,to) for (ll i=(ll)from; i<(ll)to; i++) #define all(vec) vec.begin(), vec.end() #define rep(i,N) repr(i,0,N) #define per(i,N) for (int i=(int)N-1; i>=0; i--) const ll MOD = pow(10,9)+7; const ll LLINF = pow(2,61)-1; const int INF = pow(2,30)-1; vector<ll> fac; void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; } ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; } ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; } ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); } ll lcm(ll a, ll b) { return a/gcd(a,b)*b; } // ---------------------------------------------------------------------- // ---------------------------------------------------------------------- vector<complex<double>> theta; void set_theta(ll x) { theta.resize(x); double rad = 2*M_PI / x; rep(i,x) { theta[i].real(cos(rad*i)); theta[i].imag(sin(rad*i)); } } vector<complex<double>> calc_theta(vector<complex<double>> vec) { ll l = vec.size(), s = theta.size(); if (l==1) return vec; vector<complex<double>> odd(l/2), even(l/2); rep(i,l) { if (i%2==0) even[i/2] = vec[i]; else odd[i/2] = vec[i]; } vector<complex<double>> otheta = calc_theta(odd), etheta = calc_theta(even); vector<complex<double>> result(l); rep(i,l) result[i] = theta[s/l*i]*otheta[i%(l/2)]+etheta[i%(l/2)]; return result; } vector<ll> FFT(vector<double> v1, vector<double> v2) { ll s = 1; while (s<v1.size()+v2.size()) s *= 2; set_theta(s); vector<complex<double>> vec1(s), vec2(s); rep(i,v1.size()) vec1[i].real(v1[i]); rep(i,v2.size()) vec2[i].real(v2[i]); vector<complex<double>> f1 = calc_theta(vec1), f2 = calc_theta(vec2); vector<complex<double>> fres(s); rep(i,s) fres[i] = f1[i]*f2[i]; vector<complex<double>> rtmp = calc_theta(fres); vector<ll> result(s); rep(i,s) result[i] = round((rtmp[(s-i)%s].real())/s); return result; } // ---------------------------------------------------------------------- // ---------------------------------------------------------------------- int main() { ll L, M, N; cin >> L >> M >> N; N++; ll A[L]; rep(i,L) cin >> A[i]; sort(A,A+L); ll B[M]; rep(i,M) cin >> B[i]; sort(B,B+M); ll Q; cin >> Q; ll p2 = 1; while (N>p2) p2 *= 2; set_theta(p2*4); vector<double> v1(N); rep(i,L) v1[A[i]] = 1; vector<double> v2(N); rep(i,L) v2[N-B[i]] = 1; vector<ll> v12 = FFT(v1,v2); // debug(all(result)); rep(i,Q) cout << v12[N+i] << endl; return 0; }