ProgMe

D

Jun 16th, 2023
725
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 13.44 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <iomanip>
  5. #include <valarray>
  6. #include <complex>
  7. #include <cassert>
  8.  
  9. using Cpx = std::complex<double>;
  10. const double kPI = acos(-1);
  11. std::vector<Cpx> roots = {{0, 0}, {1, 0}};
  12.  
  13. void ensureCapacity(int min_capacity) {
  14.     for (int len = roots.size(); len < min_capacity; len *= 2) {
  15.         for (int i = len >> 1; i < len; i++) {
  16.             roots.emplace_back(roots[i]);
  17.             double angle = 2 * kPI * (2 * i + 1 - len) / (len * 2);
  18.             roots.emplace_back(cos(angle), sin(angle));
  19.         }
  20.     }
  21. }
  22.  
  23. void fft(std::vector<Cpx> &z, bool inverse) {
  24.     int n = z.size();
  25.     assert((n & (n - 1)) == 0);
  26.     ensureCapacity(n);
  27.     for (unsigned i = 1, j = 0; static_cast<int>(i) < n; i++) {
  28.         int bit = n >> 1;
  29.         for (; static_cast<int>(j) >= bit; bit >>= 1) {
  30.             j -= bit;
  31.         }
  32.         j += bit;
  33.         if (i < j) {
  34.             swap(z[i], z[j]);
  35.         }
  36.     }
  37.     for (int len = 1; len < n; len <<= 1) {
  38.         for (int i = 0; i < n; i += len * 2) {
  39.             for (int j = 0; j < len; j++) {
  40.                 Cpx root = inverse ? conj(roots[j + len]) : roots[j + len];
  41.                 Cpx u = z[i + j];
  42.                 Cpx v = z[i + j + len] * root;
  43.                 z[i + j] = u + v;
  44.                 z[i + j + len] = u - v;
  45.             }
  46.         }
  47.     }
  48.     if (inverse) {
  49.         for (int i = 0; i < n; i++) {
  50.             z[i] /= n;
  51.         }
  52.     }
  53. }
  54.  
  55. std::vector<int> multiplyBigint(const std::vector<int> &a, const std::vector<int> &b, int base) {
  56.     int need = a.size() + b.size();
  57.     int n = 1;
  58.     while (n < need) {
  59.         n <<= 1;
  60.     }
  61.     std::vector<Cpx> p(n);
  62.     for (size_t i = 0; static_cast<int>(i) < n; i++) {
  63.         p[i] = Cpx(i < a.size() ? a[i] : 0, i < b.size() ? b[i] : 0);
  64.     }
  65.     fft(p, false);
  66.     // a[w[k]] = (p[w[k]] + conj(p[w[n-k]])) / 2
  67.     // b[w[k]] = (p[w[k]] - conj(p[w[n-k]])) / (2*i)
  68.     std::vector<Cpx> ab(n);
  69.     Cpx r(0, -0.25);
  70.     for (int i = 0; i < n; i++) {
  71.         int j = (n - i) & (n - 1);
  72.         ab[i] = (p[i] * p[i] - conj(p[j] * p[j])) * r;
  73.     }
  74.     fft(ab, true);
  75.     std::vector<int> result(need);
  76.     int64_t carry = 0;
  77.     for (int i = 0; i < need; i++) {
  78.         int64_t d = static_cast<int64_t>(ab[i].real() + 0.5) + carry;
  79.         carry = d / base;
  80.         result[i] = d % base;
  81.     }
  82.     return result;
  83. }
  84.  
  85. constexpr int digits(int base) noexcept {
  86.     return base <= 1 ? 0 : 1 + digits(base / 10);
  87. }
  88.  
  89. constexpr int kBase = 1000'000'000;
  90. constexpr int kBaseDigits = digits(kBase);
  91.  
  92. constexpr int kFftBase = 3000;  // fftBase^2 * n / fftBaseDigits <= 10^15 for double
  93. constexpr int kFftBaseDigits = digits(kFftBase);
  94.  
  95. struct Bigint {
  96.     // value == 0 is represented by empty z
  97.     std::vector<int> z;  // digits
  98.  
  99.     // sign == 1 <==> value >= 0
  100.     // sign == -1 <==> value < 0
  101.     int sign;
  102.  
  103.     Bigint(int64_t v = 0) {
  104.         *this = v;
  105.     }
  106.  
  107.     Bigint &operator=(int64_t v) {
  108.         sign = v < 0 ? -1 : 1;
  109.         v *= sign;
  110.         z.clear();
  111.         for (; v > 0; v = v / kBase) {
  112.             z.push_back(static_cast<int>(v % kBase));
  113.         }
  114.         return *this;
  115.     }
  116.  
  117.     Bigint(const std::string &s) {
  118.         read(s);
  119.     }
  120.  
  121.     Bigint &operator+=(const Bigint &other) {
  122.         if (sign == other.sign) {
  123.             for (int i = 0, carry = 0; i < static_cast<int>(other.z.size()) || carry; ++i) {
  124.                 if (i == static_cast<int>(z.size())) {
  125.                     z.push_back(0);
  126.                 }
  127.                 z[i] += carry + (i < static_cast<int>(other.z.size()) ? other.z[i] : 0);
  128.                 carry = z[i] >= kBase;
  129.                 if (carry) {
  130.                     z[i] -= kBase;
  131.                 }
  132.             }
  133.         } else if (other != 0 /* prevent infinite loop */) {
  134.             *this -= -other;
  135.         }
  136.         return *this;
  137.     }
  138.  
  139.     friend Bigint operator+(Bigint a, const Bigint &b) {
  140.         a += b;
  141.         return a;
  142.     }
  143.  
  144.     Bigint &operator-=(const Bigint &other) {
  145.         if (sign == other.sign) {
  146.             if ((sign == 1 && *this >= other) || (sign == -1 && *this <= other)) {
  147.                 for (int i = 0, carry = 0; i < static_cast<int>(other.z.size()) || carry; ++i) {
  148.                     z[i] -= carry + (i < static_cast<int>(other.z.size()) ? other.z[i] : 0);
  149.                     carry = z[i] < 0;
  150.                     if (carry) {
  151.                         z[i] += kBase;
  152.                     }
  153.                 }
  154.                 trim();
  155.             } else {
  156.                 *this = other - *this;
  157.                 this->sign = -this->sign;
  158.             }
  159.         } else {
  160.             *this += -other;
  161.         }
  162.         return *this;
  163.     }
  164.  
  165.     friend Bigint operator-(Bigint a, const Bigint &b) {
  166.         a -= b;
  167.         return a;
  168.     }
  169.  
  170.     Bigint &operator*=(int v) {
  171.         if (v < 0) {
  172.             sign = -sign, v = -v;
  173.         }
  174.         for (int i = 0, carry = 0; i < static_cast<int>(z.size()) || carry; ++i) {
  175.             if (i == static_cast<int>(z.size())) {
  176.                 z.push_back(0);
  177.             }
  178.             int64_t cur = static_cast<int64_t>(z[i]) * v + carry;
  179.             carry = static_cast<int>(cur / kBase);
  180.             z[i] = static_cast<int>(cur % kBase);
  181.         }
  182.         trim();
  183.         return *this;
  184.     }
  185.  
  186.     Bigint operator*(int v) const {
  187.         return Bigint(*this) *= v;
  188.     }
  189.  
  190.     friend std::pair<Bigint, Bigint> divmod(const Bigint &a1, const Bigint &b1) {
  191.         int norm = kBase / (b1.z.back() + 1);
  192.         Bigint a = a1.abs() * norm;
  193.         Bigint b = b1.abs() * norm;
  194.         Bigint q, r;
  195.         q.z.resize(a.z.size());
  196.  
  197.         for (int i = static_cast<int>(a.z.size()) - 1; i >= 0; i--) {
  198.             r *= kBase;
  199.             r += a.z[i];
  200.             int s1 = b.z.size() < r.z.size() ? r.z[b.z.size()] : 0;
  201.             int s2 = b.z.size() - 1 < r.z.size() ? r.z[b.z.size() - 1] : 0;
  202.             int d = static_cast<int>((static_cast<int64_t>(s1) * kBase + s2) / b.z.back());
  203.             r -= b * d;
  204.             while (r < 0) {
  205.                 r += b, --d;
  206.             }
  207.             q.z[i] = d;
  208.         }
  209.  
  210.         q.sign = a1.sign * b1.sign;
  211.         r.sign = a1.sign;
  212.         q.trim();
  213.         r.trim();
  214.         return {q, r / norm};
  215.     }
  216.  
  217.     Bigint operator/(const Bigint &v) const {
  218.         return divmod(*this, v).first;
  219.     }
  220.  
  221.     Bigint operator%(const Bigint &v) const {
  222.         return divmod(*this, v).second;
  223.     }
  224.  
  225.     Bigint &operator/=(int v) {
  226.         if (v < 0) {
  227.             sign = -sign, v = -v;
  228.         }
  229.         for (int i = static_cast<int>(z.size()) - 1, rem = 0; i >= 0; --i) {
  230.             int64_t cur = z[i] + rem * static_cast<int64_t>(kBase);
  231.             z[i] = static_cast<int>(cur / v);
  232.             rem = static_cast<int>(cur % v);
  233.         }
  234.         trim();
  235.         return *this;
  236.     }
  237.  
  238.     Bigint operator/(int v) const {
  239.         return Bigint(*this) /= v;
  240.     }
  241.  
  242.     int operator%(int v) const {
  243.         if (v < 0) {
  244.             v = -v;
  245.         }
  246.         int m = 0;
  247.         for (int i = static_cast<int>(z.size()) - 1; i >= 0; --i) {
  248.             m = static_cast<int>((z[i] + m * static_cast<int64_t>(kBase)) % v);
  249.         }
  250.         return m * sign;
  251.     }
  252.  
  253.     Bigint &operator*=(const Bigint &v) {
  254.         *this = *this * v;
  255.         return *this;
  256.     }
  257.  
  258.     Bigint &operator/=(const Bigint &v) {
  259.         *this = *this / v;
  260.         return *this;
  261.     }
  262.  
  263.     Bigint &operator%=(const Bigint &v) {
  264.         *this = *this % v;
  265.         return *this;
  266.     }
  267.  
  268.     bool operator<(const Bigint &v) const {
  269.         if (sign != v.sign) {
  270.             return sign < v.sign;
  271.         }
  272.         if (z.size() != v.z.size()) {
  273.             return z.size() * sign < v.z.size() * v.sign;
  274.         }
  275.         for (int i = static_cast<int>(z.size()) - 1; i >= 0; i--) {
  276.             if (z[i] != v.z[i]) {
  277.                 return z[i] * sign < v.z[i] * sign;
  278.             }
  279.         }
  280.         return false;
  281.     }
  282.  
  283.     bool operator>(const Bigint &v) const {
  284.         return v < *this;
  285.     }
  286.  
  287.     bool operator<=(const Bigint &v) const {
  288.         return !(v < *this);
  289.     }
  290.  
  291.     bool operator>=(const Bigint &v) const {
  292.         return !(*this < v);
  293.     }
  294.  
  295.     bool operator==(const Bigint &v) const {
  296.         return sign == v.sign && z == v.z;
  297.     }
  298.  
  299.     bool operator!=(const Bigint &v) const {
  300.         return !(*this == v);
  301.     }
  302.  
  303.     void trim() {
  304.         while (!z.empty() && z.back() == 0) {
  305.             z.pop_back();
  306.         }
  307.         if (z.empty()) {
  308.             sign = 1;
  309.         }
  310.     }
  311.  
  312.     bool isZero() const {
  313.         return z.empty();
  314.     }
  315.  
  316.     friend Bigint operator-(Bigint v) {
  317.         if (!v.z.empty()) {
  318.             v.sign = -v.sign;
  319.         }
  320.         return v;
  321.     }
  322.  
  323.     Bigint abs() const {
  324.         return sign == 1 ? *this : -*this;
  325.     }
  326.  
  327.     void read(const std::string &s) {
  328.         sign = 1;
  329.         z.clear();
  330.         int pos = 0;
  331.         while (pos < static_cast<int>(s.size()) && (s[pos] == '-' || s[pos] == '+')) {
  332.             if (s[pos] == '-') {
  333.                 sign = -sign;
  334.             }
  335.             ++pos;
  336.         }
  337.         for (int i = static_cast<int>(s.size()) - 1; i >= pos; i -= kBaseDigits) {
  338.             int x = 0;
  339.             for (int j = std::max(pos, i - kBaseDigits + 1); j <= i; j++) {
  340.                 x = x * 10 + s[j] - '0';
  341.             }
  342.             z.push_back(x);
  343.         }
  344.         trim();
  345.     }
  346.  
  347.     friend std::istream &operator>>(std::istream &stream, Bigint &v) {
  348.         std::string s;
  349.         stream >> s;
  350.         v.read(s);
  351.         return stream;
  352.     }
  353.  
  354.     friend std::ostream &operator<<(std::ostream &stream, const Bigint &v) {
  355.         if (v.sign == -1) {
  356.             stream << '-';
  357.         }
  358.         stream << (v.z.empty() ? 0 : v.z.back());
  359.         for (int i = static_cast<int>(v.z.size()) - 2; i >= 0; --i) {
  360.             stream << std::setw(kBaseDigits) << std::setfill('0') << v.z[i];
  361.         }
  362.         return stream;
  363.     }
  364.  
  365.     static std::vector<int> convertBase(const std::vector<int> &a, int old_digits, int new_digits) {
  366.         std::vector<int64_t> p(std::max(old_digits, new_digits) + 1);
  367.         p[0] = 1;
  368.         for (int i = 1; i < static_cast<int>(p.size()); i++) {
  369.             p[i] = p[i - 1] * 10;
  370.         }
  371.         std::vector<int> res;
  372.         int64_t cur = 0;
  373.         int cur_digits = 0;
  374.         for (int v : a) {
  375.             cur += v * p[cur_digits];
  376.             cur_digits += old_digits;
  377.             while (cur_digits >= new_digits) {
  378.                 res.push_back(int(cur % p[new_digits]));
  379.                 cur /= p[new_digits];
  380.                 cur_digits -= new_digits;
  381.             }
  382.         }
  383.         res.push_back(static_cast<int>(cur));
  384.         while (!res.empty() && res.back() == 0) {
  385.             res.pop_back();
  386.         }
  387.         return res;
  388.     }
  389.  
  390.     Bigint operator*(const Bigint &v) const {
  391.         if (std::min(z.size(), v.z.size()) < 150) {
  392.             return mulSimple(v);
  393.         }
  394.         Bigint res;
  395.         res.sign = sign * v.sign;
  396.         res.z = multiplyBigint(convertBase(z, kBaseDigits, kFftBaseDigits),
  397.                                convertBase(v.z, kBaseDigits, kFftBaseDigits), kFftBase);
  398.         res.z = convertBase(res.z, kFftBaseDigits, kBaseDigits);
  399.         res.trim();
  400.         return res;
  401.     }
  402.  
  403.     Bigint mulSimple(const Bigint &v) const {
  404.         Bigint res;
  405.         res.sign = sign * v.sign;
  406.         res.z.resize(z.size() + v.z.size());
  407.         for (int i = 0; i < static_cast<int>(z.size()); ++i) {
  408.             if (z[i]) {
  409.                 for (int j = 0, carry = 0; j < static_cast<int>(v.z.size()) || carry; ++j) {
  410.                     int64_t cur = res.z[i + j] +
  411.                                   static_cast<int64_t>(z[i]) *
  412.                                       (j < static_cast<int>(v.z.size()) ? v.z[j] : 0) +
  413.                                   carry;
  414.                     carry = static_cast<int>(cur / kBase);
  415.                     res.z[i + j] = static_cast<int>(cur % kBase);
  416.                 }
  417.             }
  418.         }
  419.         res.trim();
  420.         return res;
  421.     }
  422. };
  423.  
  424. int k_n = 800;
  425.  
  426. int n;
  427. std::vector<Bigint> f;
  428. std::vector<int> v;
  429.  
  430. void precalc() {
  431.     f[std::min(n - 1, k_n - 1)] = 1;
  432.     for (int i = std::min(k_n, n) - 2; i >= 0; i--) {
  433.         f[i] = f[i + 1] * (n - (std::min(k_n, n) - 2 - i));
  434.     }
  435. }
  436.  
  437. int main() {
  438.     std::ios::sync_with_stdio(false);
  439.     std::cin.tie(nullptr);
  440.     std::cin >> n;
  441.     Bigint kek = 1;
  442.     for (int i = 1; i <= 1000; i++) {
  443.         kek *= i;
  444.     }
  445.     Bigint meme = 1;
  446.     int noooo = std::max(n, 1000);
  447.     while (meme < kek) {
  448.         meme *= noooo;
  449.         noooo--;
  450.     }
  451.     k_n = n - noooo + 1;
  452.     f.resize(k_n);
  453.     v.resize(k_n);
  454.     precalc();
  455.     Bigint k;
  456.     std::cin >> k;
  457.     k -= 1;
  458.     for (int i = 0; i + k_n < n; i++) {
  459.         std::cout << 1 << ' ';
  460.     }
  461.     int lol = 0;
  462.     for (int i = std::max(0, n - k_n); i < n; i++) {
  463.         Bigint cnt = f[i - std::max(0, n - k_n)];
  464.         int l = 1, r = i + 1;
  465.         while (l < r) {
  466.             int m = (l + r + 1) / 2;
  467.             if (cnt * (m - 1) <= k) {
  468.                 l = m;
  469.             } else {
  470.                 r = m - 1;
  471.             }
  472.         }
  473.  
  474.         k -= cnt * (l - 1);
  475.         v[i - std::max(0, n - k_n)] = l;
  476.         lol++;
  477.     }  //
  478.     for (int i = 0; i + 1 < lol; i++) {
  479.         std::cout << v[i] << ' ';
  480.     }
  481.     std::cout << v[lol - 1];
  482. }
  483.  
Advertisement
Add Comment
Please, Sign In to add comment