• API
• FAQ
• Tools
• Archive
SHARE
TWEET

Untitled

a guest Mar 1st, 2016 945 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.
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.