BoxerTC

Untitled

Jul 24th, 2015
318
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.18 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define sc( x ) scanf( "%d" , &x )
  5. #define REP( i , n ) for( int i = 0 ; i < n ; i++ )
  6. #define clr( t , val ) memset( t , val , sizeof(t) )
  7.  
  8. #define all(v)  v.begin() , v.end()
  9. #define pb push_back
  10. #define SZ( v ) ((int)(v).size())
  11.  
  12. #define mp make_pair
  13. #define fi first
  14. #define se second
  15.  
  16. #define test() cerr << "hola que hace ?" << endl;
  17. #define DEBUG( x ) cerr <<  #x << "=" << x << endl;
  18. #define DEBUG2( x , y ) cerr << #x << "=" << x << " " << #y << "=" << y << endl;
  19.  
  20. typedef double ld;
  21. typedef vector< ld > vld;
  22. typedef long long ll;
  23. typedef vector< ll > vll;
  24. typedef pair< int , int > pii;
  25. typedef vector< int > vi;
  26.  
  27. ld PI = acos( (ld)(-1.0) );
  28.  
  29. typedef complex<ld> base;
  30.  
  31. void fft (vector<base> & a, bool invert) {
  32.     int n = (int) a.size();
  33.  
  34.     for (int i=1, j=0; i<n; ++i) {
  35.         int bit = n >> 1;
  36.         for (; j>=bit; bit>>=1)
  37.             j -= bit;
  38.         j += bit;
  39.         if (i < j)
  40.             swap (a[i], a[j]);
  41.     }
  42.  
  43.     for (int len=2; len<=n; len<<=1) {
  44.         ld ang = 2.0 * PI /len * (invert ? -1 : 1);
  45.         base wlen (cos(ang), sin(ang));
  46.         for (int i=0; i<n; i+=len) {
  47.             base w (1);
  48.             for (int j=0; j<len/2; ++j) {
  49.                 base u = a[i+j],  v = a[i+j+len/2] * w;
  50.                 a[i+j] = u + v;
  51.                 a[i+j+len/2] = u - v;
  52.                 w *= wlen;
  53.             }
  54.         }
  55.     }
  56.     if (invert)
  57.         for (int i=0; i<n; ++i)
  58.             a[i] /= n;
  59. }
  60. void multiply (const vector<ld> & a, const vector<ld> & b, vll & res) {
  61.     vector<base> fa (a.begin(), a.end()),  fb (b.begin(), b.end());
  62.     size_t n = 1;
  63.     while (n < max (a.size(), b.size()))  n <<= 1;
  64.     n <<= 1;
  65.     fa.resize (n),  fb.resize (n);
  66.  
  67.     fft (fa, false),  fft (fb, false);
  68.     for (size_t i=0; i<n; ++i)
  69.         fa[i] *= fb[i];
  70.    
  71.     fft (fa, true);
  72.  
  73.     res.resize (n);
  74.     for (size_t i=0; i<n; ++i)
  75.         res[i] = (ll)round( fa[i].real() );
  76. }
  77. int main(){
  78.     int n ,  m;
  79.     while( sc( n ) == 1 ){
  80.         vi a( n );
  81.         REP( i , n ) sc( a[ i ] );
  82.        
  83.         sc( m );
  84.         vi b( m );
  85.         REP( i , m ) sc( b[ i ] );
  86.        
  87.         int len = 200000 + 1;
  88.         vld P( len );
  89.         P[ 0 ] = 1;
  90.         REP( i , n ) P[ a[ i ] ] = 1;
  91.         vld Q = P;
  92.         vll ans;
  93.         multiply( P , Q , ans );
  94.  
  95.         int cnt = 0;
  96.         REP( i , m )
  97.             if( ans[ b[ i ] ] >= 1 ) cnt ++;
  98.        
  99.         printf( "%d\n" , cnt );
  100.     }  
  101. }
Advertisement
Add Comment
Please, Sign In to add comment