Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <deque>
- #include <fstream>
- #include <iostream>
- #include <vector>
- using namespace std;
- void sum (deque <int>& a, deque <int>& b) {
- if (a.size() < b.size()) {
- long long int dif = b.size() - a.size();
- for (size_t i = 0; i < dif; ++i) {
- a.push_front(0);
- }
- } else {
- long long int dif = a.size() - b.size();
- for (size_t i = 0; i < dif; ++i) {
- b.push_front(0);
- }
- }
- long long int size = a.size();
- int sign = (a[size - 1] + b[size - 1]) / 10;
- a[size - 1] = (a[size - 1] + b[size - 1]) % 10;
- for (long long int i = size - 2; i >= 0; --i) {
- int sign_new = (a[i] + b[i] + sign) / 10;
- a[i] = (a[i] + b[i] + sign) % 10;
- sign = sign_new;
- }
- if (sign) {
- a.push_front(1);
- }
- }
- void composition (deque <int>& a, deque <int>& b) {
- if (a.size() < b.size()) {
- deque <int> temp = a;
- a = b;
- b = temp;
- }
- int count = 0;
- for (long long int i = a.size() - 1; i >= 0; --i) {
- if (a[i] == 0) {
- ++count;
- a.pop_back();
- } else {
- break;
- }
- }
- for (long long int i = b.size() - 1; i >= 0; --i) {
- if (b[i] == 0) {
- ++count;
- b.pop_back();
- } else {
- break;
- }
- }
- vector <deque <int> > v;
- for (int j = b.size() - 1; j >= 0; --j) {
- deque <int> c = a;
- int sign = (c[c.size() - 1] * b[j]) / 10;
- c[c.size() - 1] = (c[c.size() - 1] * b[j]) % 10;
- for (long long int i = c.size() - 2; i >= 0; --i) {
- int sign_new = (c[i] * b[j] + sign) / 10;
- c[i] = (c[i] * b[j] + sign) % 10;
- sign = sign_new;
- }
- if (sign) {
- c.push_front(sign);
- }
- for (int i = j; i < b.size() - 1; ++i) {
- c.push_back(0);
- }
- v.push_back(c);
- }
- deque <int> d = {0};
- for (auto i : v) {
- sum(d, i);
- }
- for (int i = 0; i < count; ++i) {
- d.push_back(0);
- }
- a = d;
- }
- deque <int> inttodeque (int i) {
- deque <int> d;
- while (i > 0) {
- d.push_front(i % 10);
- i /= 10;
- }
- return d;
- }
- int main() {
- int a;
- freopen("input.txt", "r", stdout);
- cin >> a;
- fclose(stdout);
- deque <int> answ = {1};
- for (int i = 1; i <= a; ++i) {
- deque <int> d = inttodeque(i);
- composition(answ, d);
- }
- freopen("output.txt", "w", stdout);
- for (auto i : answ) {
- cout << i;
- }
- fclose(stdout);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement