Advertisement
Guest User

Untitled

a guest
Apr 29th, 2017
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.29 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long double ld;
  4.  
  5. const ld PI=acos(-1.0);
  6. typedef complex<ld> Complex;
  7. inline int rev_incr(int a, int n) { int msk = n/2, cnt=0;
  8. while ( a&msk ) { cnt++; a<<=1; }
  9. a &= msk-1; a |= msk;
  10. while ( cnt-- ) a >>= 1;
  11. return a; }
  12. vector<Complex> FFT(vector<Complex> v, int dir=1) {
  13. Complex wm,w,u,t; int n = v.size(); vector<Complex> V(n);
  14. for (int k=0,a=0; k<n; ++k, a=rev_incr(a,n))
  15. V[a] = v[k] / ld(dir>0 ? 1 : n);
  16. for (int m=2; m<=n; m<<=1) {
  17. wm = polar( (ld)1, dir*2*PI/m );
  18. for (int k=0; k<n; k+=m) {
  19. w = 1;
  20. for (int j=0; j<m/2; ++j, w*=wm) {
  21. u = V[k + j];
  22. t = w * V[k + j + m/2];
  23. V[k + j] = u + t;
  24. V[k + j + m/2] = u - t;
  25. } } } return V; }
  26. //! See problem 30-6 in CLRS for more details on the integer FFT
  27. //! hints for integer version:
  28. //! 440564289 and 1713844692 are inverses and 2^27th roots of 1 mod p=(15<<27)+1
  29. //! Precompute inverses for integer FFT, otherwise it will be very slow.
  30. // Multiply two polynomials sum_i a[i]x^i and sum_i b[i]x^i
  31. vector<ld> convolution(vector<ld> a, vector<ld> b) {
  32. int sz = a.size()+b.size()-1;
  33. int n = 1<<int(ceil(log2(sz)));
  34. vector<Complex> av(n,0), bv(n,0), cv;
  35. for (int i=0; i<a.size(); i++) av[i] = a[i];
  36. for (int i=0; i<b.size(); i++) bv[i] = b[i];
  37. cv = FFT(bv); bv = FFT(av);
  38. for (int i=0; i<n; i++) av[i] = bv[i]*cv[i];
  39. cv = FFT(av, -1);
  40. // cv is now the convolution of a and b: cv[k] = sum_(i+j=k) a[i]*b[j]
  41. vector<ld> c(sz);
  42. for (int i=0; i<sz; i++)
  43. c[i] = cv[i].real(); // if result should be int, use int(cv[i].real()+0.5)
  44. return c; }
  45.  
  46. int main(){
  47. ios::sync_with_stdio(0);
  48. int n; cin>>n;
  49. vector<ld> a;
  50. for (int i=0;i<n;i++){
  51. int x; cin>>x;
  52. while (a.size()<=x) a.push_back(0);
  53. a[x]=1;
  54. }
  55. int ans=0;
  56. int m; cin>>m;
  57. vector<ld> res=convolution(a,a);
  58. //for (ld x:a) cout<<x<<" "; cout<<endl;
  59. //for (ld x:res) cout<<x<<" "; cout<<endl;
  60. while (m--){
  61. int x; cin>>x;
  62. if (((x<res.size())&&(res[x]>0.5))||((x<a.size())&&(a[x]>0.5))) {
  63. ans++;
  64. }
  65. }
  66. cout<<ans<<endl;
  67. return 0;
  68. }
  69.  
  70. //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