Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long double ld;
- const ld PI=acos(-1.0);
- typedef complex<ld> Complex;
- inline int rev_incr(int a, int n) { int msk = n/2, cnt=0;
- while ( a&msk ) { cnt++; a<<=1; }
- a &= msk-1; a |= msk;
- while ( cnt-- ) a >>= 1;
- return a; }
- vector<Complex> FFT(vector<Complex> v, int dir=1) {
- Complex wm,w,u,t; int n = v.size(); vector<Complex> V(n);
- for (int k=0,a=0; k<n; ++k, a=rev_incr(a,n))
- V[a] = v[k] / ld(dir>0 ? 1 : n);
- for (int m=2; m<=n; m<<=1) {
- wm = polar( (ld)1, dir*2*PI/m );
- for (int k=0; k<n; k+=m) {
- w = 1;
- for (int j=0; j<m/2; ++j, w*=wm) {
- u = V[k + j];
- t = w * V[k + j + m/2];
- V[k + j] = u + t;
- V[k + j + m/2] = u - t;
- } } } return V; }
- //! See problem 30-6 in CLRS for more details on the integer FFT
- //! hints for integer version:
- //! 440564289 and 1713844692 are inverses and 2^27th roots of 1 mod p=(15<<27)+1
- //! Precompute inverses for integer FFT, otherwise it will be very slow.
- // Multiply two polynomials sum_i a[i]x^i and sum_i b[i]x^i
- vector<ld> convolution(vector<ld> a, vector<ld> b) {
- int sz = a.size()+b.size()-1;
- int n = 1<<int(ceil(log2(sz)));
- vector<Complex> av(n,0), bv(n,0), cv;
- for (int i=0; i<a.size(); i++) av[i] = a[i];
- for (int i=0; i<b.size(); i++) bv[i] = b[i];
- cv = FFT(bv); bv = FFT(av);
- for (int i=0; i<n; i++) av[i] = bv[i]*cv[i];
- cv = FFT(av, -1);
- // cv is now the convolution of a and b: cv[k] = sum_(i+j=k) a[i]*b[j]
- vector<ld> c(sz);
- for (int i=0; i<sz; i++)
- c[i] = cv[i].real(); // if result should be int, use int(cv[i].real()+0.5)
- return c; }
- int main(){
- ios::sync_with_stdio(0);
- int n; cin>>n;
- vector<ld> a;
- for (int i=0;i<n;i++){
- int x; cin>>x;
- while (a.size()<=x) a.push_back(0);
- a[x]=1;
- }
- int ans=0;
- int m; cin>>m;
- vector<ld> res=convolution(a,a);
- //for (ld x:a) cout<<x<<" "; cout<<endl;
- //for (ld x:res) cout<<x<<" "; cout<<endl;
- while (m--){
- int x; cin>>x;
- if (((x<res.size())&&(res[x]>0.5))||((x<a.size())&&(a[x]>0.5))) {
- ans++;
- }
- }
- cout<<ans<<endl;
- return 0;
- }
- //g++ -std=c++11 -O2 -Wfatal-errors -Im -Wall -Wextra -o "output.txt" "code.cpp"
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement