SHARE
TWEET

Untitled

edvard_davtyan Mar 1st, 2016 489 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <string>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <vector>
  7. #include <stack>
  8. #include <queue>
  9. #include <list>
  10. #include <map>
  11. #include <set>
  12. #include <stdlib.h>
  13. #include <sstream>
  14. #include <assert.h>
  15. #include <memory.h>
  16. #include <complex>
  17.  
  18. #include <time.h>
  19. #pragma comment(linker, "/STACK:20000000")
  20.  
  21. #define fr(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
  22. #define fd(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
  23. #define mp make_pair
  24. #define pb push_back
  25. #define ll long long
  26.  
  27. using namespace std;
  28.  
  29. int ri(){int x;scanf("%d",&x);return x;}
  30. ll rll(){ll x;scanf("%lld",&x);return x;}
  31.  
  32. typedef complex<double> base;
  33. const double PI = acos(-1.0);
  34. vector<int> order;
  35.  
  36. void fft (vector<base> &a,bool invert)
  37. {
  38.     int n = a.size();
  39.     for(int i = 0;i < n;i++)
  40.         if (order[i] < i)
  41.             swap(a[i],a[order[i]]);
  42.     for (int len = 2; len <= n; len <<= 1)
  43.     {
  44.         double ang = 2 * PI / len * (invert ? -1 : 1);
  45.         base wlen (cos(ang), sin(ang));
  46.         int half = len >> 1;
  47.         vector<base> w(half);
  48.         base w0(1);
  49.         for(int i = 0;i < half;i++)
  50.             w[i] = w0,w0 *= wlen;
  51.         for (int i = 0; i < n; i += len)
  52.         {
  53.             for (int j = 0; j < half; j++)
  54.             {
  55.                 base u = a[i + j];
  56.                 base v = a[i + j + half] * w[j];
  57.                 a[i + j] = u + v;
  58.                 a[i + j + half] = u - v;
  59.             }
  60.         }
  61.     }
  62.     if (invert)
  63.         for (int i = 0; i < n; i++)
  64.             a[i] /= n;
  65. }
  66.  
  67. void precalc(int n,int L)
  68. {
  69.     order.resize(n);
  70.     for(int i = 0;i < n;i++)
  71.     {
  72.         int res = 0;
  73.         for(int j = 0;j < L;j++)
  74.             if (i & (1<<j))
  75.                 res |= 1<<(L - j - 1);
  76.         order[i] = res;
  77.     }
  78. }
  79.  
  80. vector<int> fft_mul(vector<int> a,vector<int> b)
  81. {
  82.     vector<base> fa(a.begin(),a.end()),fb(b.begin(),b.end());
  83.     int n = 1;
  84.     int L = 0;
  85.     while(a.size() + b.size() > n)
  86.         n <<= 1,L++;
  87.     fa.resize(n);
  88.     fb.resize(n);
  89.     precalc(n,L);
  90.     fft(fa,false);
  91.     fft(fb,false);
  92.     for(int i = 0;i < n;i++)
  93.         fa[i] *= fb[i];
  94.     fft(fa,true);
  95.  
  96.     vector<int> res(n);
  97.     for(int i = 0;i < n;i++)
  98.     {
  99.         res[i] = (int)(fa[i].real() + 0.5);
  100.         res[i] = min(res[i],1);
  101.     }
  102.     while(res.back() == 0 && res.size() > 1)
  103.         res.pop_back();
  104.     return res;
  105. }
  106.  
  107. int wtf[10050];
  108.  
  109. void solve()
  110. {
  111.     int n = ri(),m = ri();
  112.     if (m == 0)
  113.     {
  114.         cout << 1 << endl;
  115.         return;
  116.     }
  117.     vector<int> y;
  118.     for(int i = 1;i <= n;i++)
  119.         wtf[ri()] = 1;
  120.     for(int i = 0;i <= 1000;i++)
  121.         y.pb(wtf[i]);
  122.     vector<int> z (1,1);
  123.     while(m)
  124.     {
  125.         if (m & 1)
  126.             z = fft_mul(z,y);
  127.         y = fft_mul(y,y);
  128.         m >>= 1;
  129.     }
  130.     for(int i = 0;i < z.size();i++)
  131.         if (z[i])
  132.             printf("%d ",i);
  133. }
  134.  
  135. int main()
  136. {
  137.     #ifndef ONLINE_JUDGE
  138.         freopen("C:/Users/CleRIC/Desktop/������/acm.timus.ru/input.txt","rt",stdin);
  139.         freopen("C:/Users/CleRIC/Desktop/������/acm.timus.ru/output.txt","wt",stdout);
  140.     #else
  141.         //freopen("input.in","rt",stdin);
  142.         //freopen("output.out","wt",stdout);
  143.     #endif
  144.  
  145.     solve();
  146.  
  147.     #ifndef ONLINE_JUDGE
  148.         printf("\n\ntime-%.3lf",clock()*1e-3);
  149.     #endif
  150.  
  151.     return 0;
  152. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top