Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #pragma GCC optimize("O3")
- #pragma GCC target("avx2")
- using namespace std;
- vector<vector<unsigned>> a;
- const int K = 384;
- vector<unsigned> dumb_mul(vector<unsigned> &a, vector<unsigned> &b) {
- int sz = max(a.size(), b.size());
- sz += sz & 1;
- vector<unsigned> ans(2 * sz);
- for (int i = 0; i < a.size(); i++) {
- for (int j = 0; j < b.size(); j++) {
- ans[i + j] += a[i] * b[j];
- }
- }
- return ans;
- }
- vector<unsigned> mul(vector<unsigned> &a, vector<unsigned> &b) {
- int sz = max(a.size(), b.size());
- if (min(a.size(), b.size()) <= K) {
- return dumb_mul(a, b);
- }
- sz += sz & 1;
- a.resize(sz);
- b.resize(sz);
- vector<unsigned> A(sz / 2), B(sz / 2), C(sz / 2), D(sz / 2);
- for (int i = sz / 2; i < sz; i++) A[i - sz / 2] = a[i];
- for (int i = sz / 2; i < sz; i++) C[i - sz / 2] = b[i];
- for (int i = 0; i < sz / 2; i++) B[i] = a[i];
- for (int i = 0; i < sz / 2; i++) D[i] = b[i];
- vector<unsigned> AC = mul(A, C);
- vector<unsigned> BD = mul(B, D);
- vector<unsigned> apb(sz / 2), cpd(sz / 2);
- for (int i = 0; i < sz / 2; i++) apb[i] = A[i] + B[i], cpd[i] = C[i] + D[i];
- vector<unsigned> L = mul(apb, cpd);
- vector<unsigned> ans(2 * sz);
- for (int i = 0; i < sz; i++) ans[i] += BD[i];
- for (int i = sz; i < 2 * sz; i++) ans[i] += AC[i - sz];
- for (int i = 0; i < sz; i++) ans[i + sz / 2] += L[i] - AC[i] - BD[i];
- return ans;
- }
- vector<unsigned> go(int l, int r) {
- if (l == r) return a[l];
- int m = (l + r) / 2;
- vector<unsigned> x1 = go(l, m), x2 = go(m + 1, r);
- int sz = x1.size() + x2.size() - 1;
- vector<unsigned> ans = mul(x1, x2);
- ans.resize(sz);
- return ans;
- }
- signed main(){
- ios::sync_with_stdio(0);
- cin.tie(0);
- string s;
- int sum = 0;
- while(getline(cin, s)) {
- s += ' ';
- vector<unsigned> k;
- int cur = 0;
- for (auto i : s) {
- if (i != ' ') cur *= 10, cur += i - '0';
- else k.push_back(cur), cur = 0;
- }
- a.push_back(k);
- sum += k.size() - 1;
- }
- int sz = a.size();
- vector<unsigned> ans = go(0, sz - 1);
- ans.resize(sum + 1);
- for (auto i : ans) cout << i << " ";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement