SHARE
TWEET

Untitled

a guest Mar 1st, 2016 906 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 long 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. const int LOGN = 20, N = (1 << LOGN) + 3;
  44.  
  45. namespace fftMod {
  46.     typedef int T;
  47.     li mul(li a, li b, li mod) {
  48.         li q = li(ld(a) * b / mod);
  49.         li ans = (a * b - q * mod) % mod;
  50.         return ans < 0 ? ans + mod : ans;
  51.     }
  52.     int mul(int a, int b, int mod) { return int(a * 1ll * b % mod); }
  53.     T add(T a, T b, T mod) { return a + b >= mod ? (a + b - mod) : (a + b); }
  54.     T sub(T a, T b, T mod) { return add(a, mod - b, mod); }
  55.     T gcd(T a, T b, T& x, T& y) {
  56.         if (!a) {
  57.             x = 0, y = 1;
  58.             return b;
  59.         }
  60.         T xx, yy, g = gcd(b % a, a, xx, yy);
  61.         x = yy - b / a * xx;
  62.         y = xx;
  63.         return g;
  64.     }
  65.     T inv(T a, T mod) {
  66.         T x, y;
  67.         assert(gcd(a, mod, x, y) == 1);
  68.         x %= mod;
  69.         (x < 0) && (x += mod);
  70.         return x;
  71.     }
  72.     T binPow(T a, T b, T mod) {
  73.         T ans = 1;
  74.         while (b) {
  75.             if (b & 1) ans = mul(ans, a, mod);
  76.             a = mul(a, a, mod);
  77.             b >>= 1;
  78.         }
  79.         return ans;
  80.     }
  81.  
  82.     int logn, n;
  83.     T p, g;
  84.     int get(int i) {
  85.         int ans = 0;
  86.         forn(j, logn) if (i & (1 << j)) ans |= 1 << (logn - 1 - j);
  87.         return ans;
  88.     }
  89.     void fft(T *a, bool inverse) {
  90.         forn(i, n) {
  91.             int ni = get(i);
  92.             if (i < ni) swap(a[i], a[ni]);
  93.         }
  94.         assert(binPow(g, n, p) == 1);
  95.         for (int i = 0; i < logn; i++) {
  96.             T cg = binPow(g, 1 << (logn - (i + 1)), p);
  97.             assert(binPow(cg, 1 << (i + 1), p) == 1);
  98.             assert(binPow(cg, 1 << i, p) != 1);
  99.             if (inverse) cg = inv(cg, p);
  100.             for (int j = 0; j < n; j += (1 << (i + 1))) {
  101.                 T cur = 1;
  102.                 for (int k = 0; k < (1 << i); k++) {
  103.                     T u = a[j + k], v = mul(a[j + (1 << i) + k], cur, p);
  104.                     a[j + k] = add(u, v, p);
  105.                     a[j + (1 << i) + k] = sub(u, v, p);
  106.                     cur = mul(cur, cg, p);
  107.                 }
  108.             }
  109.         }
  110.         if (inverse) forn(i, n) a[i] = mul(a[i], inv(n, p), p);
  111.     }
  112.     // p                   | deg | g
  113.     // 469762049             26    3
  114.     // 998244353             23    3
  115.     // 1107296257            24    10
  116.     // 10000093151233        26    5
  117.     // 1000000523862017      26    3
  118.     // 1000000000949747713   26    2
  119.     void prepare() {
  120.         p = 469762049; // You can use your own p = c * 2^logn + 1
  121.         g = 3;         // but you should find it's generator
  122.         assert(!((p - 1) & (n - 1)));
  123.         T cs = (p - 1) >> logn;
  124.         g = binPow(g, cs, p);
  125.     }
  126.     void mul(T *a, int na, T *b, int nb, T *ans) {
  127.         while (na && !a[na - 1]) na--;
  128.         while (nb && !b[nb - 1]) nb--;
  129.         logn = 0; while ((1 << logn) < na + nb) logn++;
  130.         n = 1 << logn;
  131.  
  132.         static T _b[N];
  133.         forn(i, n) ans[i] = a[i], _b[i] = b[i];
  134.         prepare();
  135.         fft(ans, false);
  136.         fft(_b, false);
  137.         forn(i, n) ans[i] = mul(ans[i], _b[i], p);
  138.         fft(ans, true);
  139.     }
  140. };
  141.  
  142. void mul(int* a, int* b) {
  143.     forn(i, 1 << LOGN) {
  144.         a[i] = !!a[i];
  145.         b[i] = !!b[i];
  146.     }
  147.     fftMod::mul(a, 1 << LOGN, b, 1 << LOGN, a);
  148. }
  149.  
  150. void binPow(int* a, int b) {
  151.     static int ans[N];
  152.     forn(i, 1 << LOGN) ans[i] = !i;
  153.     while (b) {
  154.         if (b & 1) mul(ans, a);
  155.         mul(a, a);
  156.         b >>= 1;
  157.     }
  158.     forn(i, 1 << LOGN) a[i] = ans[i];
  159. }
  160.  
  161. void solve() {
  162.     static int ans[N];
  163.     memset(ans, 0, sizeof(ans));
  164.     forn(i, sz(a)) ans[a[i]] = 1;
  165.  
  166.     binPow(ans, k);
  167.  
  168.     bool f = true;
  169.     forn(i, 1 << LOGN)
  170.         if (ans[i]) {
  171.             if (f) f = false;
  172.             else putchar(' ');
  173.             printf("%d", i);
  174.         }
  175.     puts("");
  176. }
  177.  
  178. int main() {
  179. #ifdef SU1
  180.     assert(freopen("input.txt", "rt", stdin));
  181.     //assert(freopen("output.txt", "wt", stdout));
  182. #endif
  183.    
  184.     cout << setprecision(10) << fixed;
  185.     cerr << setprecision(5) << fixed;
  186.  
  187.     while (read()) {
  188.         ld stime = gett();
  189.         solve();
  190.         cerr << "Time: " << gett() - stime << endl;
  191.         //break;
  192.     }
  193.    
  194.     return 0;
  195. }
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