Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ∧_∧
- ( ・ω・。)つ━☆・*。
- ⊂ ノ ・゜
- しーJ Accepted
- */
- // #pragma GCC optimize("O3")
- // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #include<bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #define ll long long
- #define all(x) begin(x), end(x)
- #define x first
- #define y second
- #define int unsigned int
- using namespace std;
- using namespace __gnu_pbds;
- typedef pair<int, int> pii;
- typedef long double ld;
- template<typename T>
- using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
- const ld PI = atan2(0, -1);
- void seriy() {
- // ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cout << fixed << setprecision(14);
- #ifdef _offline
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- }
- const int MAXN = 100 + 10;
- const int MAXM = 600;
- const int INF = INT_MAX;
- const int MOD = 1e9 + 7;
- const int MAXLOG = 61;
- void simple_multiply(vector<int> &a, vector<int> &b, vector<int> &res) {
- res.resize(a.size() + b.size());
- for(int i = 0; i < b.size(); i++) {
- for(int j = 0; j < a.size(); j++) {
- res[i + j] += b[i] * a[j];
- }
- }
- }
- void sum(vector<int> &a, vector<int> &b, vector<int> &res) {
- res.resize(max(a.size(), b.size()));
- if(a.size() < b.size()) {
- swap(a, b);
- }
- res = a;
- for(int i = 0; i < b.size(); i++) {
- res[i] += b[i];
- }
- }
- void out(vector<int> &a) {
- for(auto i : a) {
- cerr << i << " ";
- }
- cerr << '\n';
- }
- void multiply(vector<int> &a, vector<int> &b, vector<int> &res) {
- if(max(a.size(), b.size()) < 100) {
- simple_multiply(a, b, res);
- return;
- }
- if(a.size() < b.size()) {
- swap(a, b);
- }
- while(b.size() < a.size()) {
- b.push_back(0);
- }
- while((b.size() & (b.size() - 1))) {
- a.push_back(0);
- b.push_back(0);
- }
- int mid = a.size() / 2;
- vector<int> al, ar, bl, br;
- for(int i = 0; i < a.size(); i++) {
- if(i < mid) {
- al.push_back(a[i]);
- bl.push_back(b[i]);
- }
- else {
- ar.push_back(a[i]);
- br.push_back(b[i]);
- }
- }
- vector<int> r1, r2, r3, r4;
- multiply(al, bl, r1);
- multiply(al, br, r2);
- multiply(ar, bl, r3);
- multiply(ar, br, r4);
- reverse(all(r1));
- reverse(all(r2));
- reverse(all(r3));
- reverse(all(r4));
- // res.resize(a.size() + b.size() - 1);
- for(int i = 0; i < mid; i++) {
- r2.push_back(0);
- }
- for(int i = 0; i < mid; i++) {
- r3.push_back(0);
- }
- for(int i = 0; i < 2 * mid; i++) {
- r4.push_back(0);
- }
- reverse(all(r1));
- reverse(all(r2));
- reverse(all(r3));
- reverse(all(r4));
- // out(r1);
- // out(r2);
- // out(r3);
- // out(r4);
- sum(r1, r2, res);
- vector<int> res2;
- sum(res, r3, res2);
- res = {};
- sum(res2, r4, res);
- }
- signed main() {
- seriy();
- vector<vector<int>> a;
- string s;
- while(getline(cin, s)) {
- a.push_back(vector<int>());
- stringstream ss(s);
- string w;
- while(ss >> w) {
- a.back().push_back(stoi(w));
- }
- }
- for(int i = 0; i < a.size() - 1; i++) {
- vector<int> res;
- multiply(a[i], a[i + 1], res);
- a[i + 1] = res;
- while(a[i + 1].back() == 0) {
- a[i + 1].pop_back();
- }
- }
- bool was = 0;
- for(auto i : a.back()) {
- cout << i << " ";
- }
- //1 4 13 18 18
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement