SHARE
TWEET

Untitled

a guest Mar 1st, 2016 1,072 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define forn(i, n) for (int i = 0; i < int(n); i++)
  4. #define nfor(i, n) for (int i = int(n) - 1; i >= 0; i--)
  5. #define fore(i, l, r) for (int i = int(l); i < int(r); i++)
  6. #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
  7. #define all(a) (a).begin(), (a).end()
  8. #define sz(a) int((a).size())
  9. #define pb(a) push_back(a)
  10. #define mp(x, y) make_pair((x), (y))
  11. #define x first
  12. #define y second
  13.  
  14. using namespace std;
  15.  
  16. typedef long long li;
  17. typedef double ld;
  18. typedef pair<int, int> pt;
  19.  
  20. template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
  21. template<typename X> inline X sqr(const X& a) { return a * a; }
  22.  
  23. template<typename A, typename B> inline ostream& operator<< (ostream& out, const pair<A, B>& p) { return out << "(" << p.x << ", " << p.y << ")"; }
  24. template<typename T> inline ostream& operator<< (ostream& out, const vector<T>& a) { out << "["; forn(i, sz(a)) { if (i) out << ','; out << ' ' << a[i]; } return out << " ]"; }
  25. template<typename T> inline ostream& operator<< (ostream& out, const set<T>& a) { return out << vector<T>(all(a)); }
  26.  
  27. inline ld gett() { return ld(clock()) / CLOCKS_PER_SEC; }
  28.  
  29. const int INF = int(1e9);
  30. const li INF64 = li(1e18);
  31. const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
  32.  
  33. int n, k;
  34. vector<int> a;
  35.  
  36. bool read() {
  37.     if (!(cin >> n >> k)) return false;
  38.     a.resize(n);
  39.     forn(i, n) assert(scanf("%d", &a[i]) == 1);
  40.     return true;
  41. }
  42.  
  43. struct base {
  44.     ld re, im;
  45.     base() { }
  46.     base(ld re, ld im): re(re), im(im) { }
  47.     ld slen() const { return sqr(re) + sqr(im); }
  48.     ld real() { return re; }
  49. };
  50.  
  51. inline base conj(const base& a) { return base(a.re, -a.im); }
  52. inline base operator+ (const base& a, const base& b) { return base(a.re + b.re, a.im + b.im); }
  53. inline base operator- (const base& a, const base& b) { return base(a.re - b.re, a.im - b.im); }
  54. inline base operator* (const base& a, const base& b) { return base(a.re * b.re - a.im * b.im, a.re * b.im + a.im * b.re); }
  55. inline base operator/ (const base& a, const ld& b) { return base(a.re / b, a.im / b); }
  56. inline base operator/ (const base& a, const base& b) { return base(a.re * b.re + a.im * b.im, a.im * b.re - a.re * b.im) / b.slen(); }
  57. inline base& operator/= (base& a, const ld& b) { a.re /= b, a.im /= b; return a; }
  58.  
  59. int reverse(int x, int logn) {
  60.     int ans = 0;
  61.     forn(i, logn) if (x & (1 << i)) ans |= 1 << (logn - 1 - i);
  62.     return ans;
  63. }
  64.  
  65. const int LOGN = 20, N = (1 << LOGN) + 3;
  66. void fft(base a[N], int n, bool inv) {
  67.     static base vv[LOGN][N];
  68.     static bool prepared = false;
  69.     if (!prepared) {
  70.         prepared = true;
  71.         forn(i, LOGN) {
  72.             ld ang = 2 * PI / (1 << (i + 1));
  73.             forn(j, 1 << i) vv[i][j] = base(cos(ang * j), sin(ang * j));
  74.         }
  75.     }
  76.     int logn = 0; while ((1 << logn) < n) logn++;
  77.     forn(i, n) {
  78.         int ni = reverse(i, logn);
  79.         if (i < ni) swap(a[i], a[ni]);
  80.     }
  81.     for (int i = 0; (1 << i) < n; i++)
  82.         for (int j = 0; j < n; j += (1 << (i + 1)))
  83.             for (int k = j; k < j + (1 << i); k++) {
  84.                 base cur = inv ? conj(vv[i][k - j]) : vv[i][k - j];
  85.                 base l = a[k], r = cur * a[k + (1 << i)];
  86.                 a[k] = l + r;
  87.                 a[k + (1 << i)] = l - r;
  88.             }
  89.     if (inv) forn(i, n) a[i] /= ld(n);
  90. }
  91.  
  92. void mul(int a[N], int b[N], int ans[N]) {
  93.     static base fp[N], p1[N], p2[N];
  94.     int n = 1 << LOGN, m = 1 << LOGN;
  95.     while (n && !a[n - 1]) n--;
  96.     while (m && !b[m - 1]) m--;
  97.     int cnt = n + m;
  98.     while (cnt & (cnt - 1)) cnt++;
  99.     if (cnt > (1 << LOGN)) return;
  100.    
  101.     forn(i, cnt) fp[i] = base(a[i], b[i]);
  102.     fft(fp, cnt, false);
  103.     forn(i, cnt) {
  104.         p1[i] = (fp[i] + conj(fp[(cnt - i) % cnt])) / base(2, 0);
  105.         p2[i] = (fp[i] - conj(fp[(cnt - i) % cnt])) / base(0, 2);
  106.     }
  107.     forn(i, cnt) fp[i] = p1[i] * p2[i];
  108.     fft(fp, cnt, true);
  109.  
  110.     forn(i, cnt) ans[i] = int(fp[i].real() + 0.5);
  111. }
  112.  
  113. void mul(int* a, int* b) {
  114.     forn(i, 1 << LOGN) {
  115.         a[i] = !!a[i];
  116.         b[i] = !!b[i];
  117.     }
  118.     mul(a, b, a);
  119. }
  120.  
  121. void binPow(int* a, int b) {
  122.     static int ans[N];
  123.     forn(i, 1 << LOGN) ans[i] = !i;
  124.     while (b) {
  125.         if (b & 1) mul(ans, a);
  126.         mul(a, a);
  127.         b >>= 1;
  128.     }
  129.     forn(i, 1 << LOGN) a[i] = ans[i];
  130. }
  131.  
  132. void solve() {
  133.     static int ans[N];
  134.     memset(ans, 0, sizeof(ans));
  135.     forn(i, sz(a)) ans[a[i]] = 1;
  136.  
  137.     binPow(ans, k);
  138.  
  139.     bool f = true;
  140.     forn(i, 1 << LOGN)
  141.         if (ans[i]) {
  142.             if (f) f = false;
  143.             else putchar(' ');
  144.             printf("%d", i);
  145.         }
  146.     puts("");
  147. }
  148.  
  149. int main() {
  150. #ifdef SU1
  151.     assert(freopen("input.txt", "rt", stdin));
  152.     //assert(freopen("output.txt", "wt", stdout));
  153. #endif
  154.    
  155.     cout << setprecision(10) << fixed;
  156.     cerr << setprecision(5) << fixed;
  157.  
  158.     while (read()) {
  159.         ld stime = gett();
  160.         solve();
  161.         cerr << "Time: " << gett() - stime << endl;
  162.         //break;
  163.     }
  164.    
  165.     return 0;
  166. }
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