Advertisement
Guest User

Untitled

a guest
Nov 20th, 2019
125
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.27 KB | None | 0 0
  1.  
  2. #include <bits/stdc++.h>
  3. #pragma GCC optimize("O3")
  4. #pragma GCC target("avx2")
  5. using namespace std;
  6.  
  7. vector<vector<unsigned>> a;
  8. const int K = 384;
  9.  
  10. vector<unsigned> dumb_mul(vector<unsigned> &a, vector<unsigned> &b) {
  11.     int sz = max(a.size(), b.size());
  12.     sz += sz & 1;
  13.     vector<unsigned> ans(2 * sz);
  14.     for (int i = 0; i < a.size(); i++) {
  15.         for (int j = 0; j < b.size(); j++) {
  16.             ans[i + j] += a[i] * b[j];
  17.         }
  18.     }
  19.     return ans;
  20. }
  21.  
  22. vector<unsigned> mul(vector<unsigned> &a, vector<unsigned> &b) {
  23.     int sz = max(a.size(), b.size());
  24.     if (min(a.size(), b.size()) <= K) {
  25.         return dumb_mul(a, b);
  26.     }
  27.     sz += sz & 1;
  28.     a.resize(sz);
  29.     b.resize(sz);
  30.     vector<unsigned> A(sz / 2), B(sz / 2), C(sz / 2), D(sz / 2);
  31.     for (int i = sz / 2; i < sz; i++) A[i - sz / 2] = a[i];
  32.     for (int i = sz / 2; i < sz; i++) C[i - sz / 2] = b[i];
  33.     for (int i = 0; i < sz / 2; i++) B[i] = a[i];
  34.     for (int i = 0; i < sz / 2; i++) D[i] = b[i];
  35.     vector<unsigned> AC = mul(A, C);
  36.     vector<unsigned> BD = mul(B, D);
  37.     vector<unsigned> apb(sz / 2), cpd(sz / 2);
  38.     for (int i = 0; i < sz / 2; i++) apb[i] = A[i] + B[i], cpd[i] = C[i] + D[i];
  39.     vector<unsigned> L = mul(apb, cpd);
  40.     vector<unsigned> ans(2 * sz);
  41.     for (int i = 0; i < sz; i++) ans[i] += BD[i];
  42.     for (int i = sz; i < 2 * sz; i++) ans[i] += AC[i - sz];
  43.     for (int i = 0; i < sz; i++) ans[i + sz / 2] += L[i] - AC[i] - BD[i];
  44.     return ans;
  45. }
  46.  
  47. vector<unsigned> go(int l, int r) {
  48.     if (l == r) return a[l];
  49.     int m = (l + r) / 2;
  50.     vector<unsigned> x1 = go(l, m), x2 = go(m + 1, r);
  51.     int sz = x1.size() + x2.size() - 1;
  52.     vector<unsigned> ans = mul(x1, x2);
  53.     ans.resize(sz);
  54.     return ans;
  55. }
  56.  
  57. signed main(){
  58.     ios::sync_with_stdio(0);
  59.     cin.tie(0);
  60.     string s;
  61.     int sum = 0;
  62.     while(getline(cin, s)) {
  63.         s += ' ';
  64.         vector<unsigned> k;
  65.         int cur = 0;
  66.         for (auto i : s) {
  67.             if (i != ' ') cur *= 10, cur += i - '0';
  68.             else k.push_back(cur), cur = 0;
  69.         }
  70.         a.push_back(k);
  71.         sum += k.size() - 1;
  72.     }
  73.     int sz = a.size();
  74.     vector<unsigned> ans = go(0, sz - 1);
  75.     ans.resize(sum + 1);
  76.     for (auto i : ans) cout << i << " ";
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement