SHARE
TWEET

Untitled

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