Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- #include <iomanip>
- #include <valarray>
- #include <complex>
- #include <cassert>
- using Cpx = std::complex<double>;
- const double kPI = acos(-1);
- std::vector<Cpx> roots = {{0, 0}, {1, 0}};
- void ensureCapacity(int min_capacity) {
- for (int len = roots.size(); len < min_capacity; len *= 2) {
- for (int i = len >> 1; i < len; i++) {
- roots.emplace_back(roots[i]);
- double angle = 2 * kPI * (2 * i + 1 - len) / (len * 2);
- roots.emplace_back(cos(angle), sin(angle));
- }
- }
- }
- void fft(std::vector<Cpx> &z, bool inverse) {
- int n = z.size();
- assert((n & (n - 1)) == 0);
- ensureCapacity(n);
- for (unsigned i = 1, j = 0; static_cast<int>(i) < n; i++) {
- int bit = n >> 1;
- for (; static_cast<int>(j) >= bit; bit >>= 1) {
- j -= bit;
- }
- j += bit;
- if (i < j) {
- swap(z[i], z[j]);
- }
- }
- for (int len = 1; len < n; len <<= 1) {
- for (int i = 0; i < n; i += len * 2) {
- for (int j = 0; j < len; j++) {
- Cpx root = inverse ? conj(roots[j + len]) : roots[j + len];
- Cpx u = z[i + j];
- Cpx v = z[i + j + len] * root;
- z[i + j] = u + v;
- z[i + j + len] = u - v;
- }
- }
- }
- if (inverse) {
- for (int i = 0; i < n; i++) {
- z[i] /= n;
- }
- }
- }
- std::vector<int> multiplyBigint(const std::vector<int> &a, const std::vector<int> &b, int base) {
- int need = a.size() + b.size();
- int n = 1;
- while (n < need) {
- n <<= 1;
- }
- std::vector<Cpx> p(n);
- for (size_t i = 0; static_cast<int>(i) < n; i++) {
- p[i] = Cpx(i < a.size() ? a[i] : 0, i < b.size() ? b[i] : 0);
- }
- fft(p, false);
- // a[w[k]] = (p[w[k]] + conj(p[w[n-k]])) / 2
- // b[w[k]] = (p[w[k]] - conj(p[w[n-k]])) / (2*i)
- std::vector<Cpx> ab(n);
- Cpx r(0, -0.25);
- for (int i = 0; i < n; i++) {
- int j = (n - i) & (n - 1);
- ab[i] = (p[i] * p[i] - conj(p[j] * p[j])) * r;
- }
- fft(ab, true);
- std::vector<int> result(need);
- int64_t carry = 0;
- for (int i = 0; i < need; i++) {
- int64_t d = static_cast<int64_t>(ab[i].real() + 0.5) + carry;
- carry = d / base;
- result[i] = d % base;
- }
- return result;
- }
- constexpr int digits(int base) noexcept {
- return base <= 1 ? 0 : 1 + digits(base / 10);
- }
- constexpr int kBase = 1000'000'000;
- constexpr int kBaseDigits = digits(kBase);
- constexpr int kFftBase = 3000; // fftBase^2 * n / fftBaseDigits <= 10^15 for double
- constexpr int kFftBaseDigits = digits(kFftBase);
- struct Bigint {
- // value == 0 is represented by empty z
- std::vector<int> z; // digits
- // sign == 1 <==> value >= 0
- // sign == -1 <==> value < 0
- int sign;
- Bigint(int64_t v = 0) {
- *this = v;
- }
- Bigint &operator=(int64_t v) {
- sign = v < 0 ? -1 : 1;
- v *= sign;
- z.clear();
- for (; v > 0; v = v / kBase) {
- z.push_back(static_cast<int>(v % kBase));
- }
- return *this;
- }
- Bigint(const std::string &s) {
- read(s);
- }
- Bigint &operator+=(const Bigint &other) {
- if (sign == other.sign) {
- for (int i = 0, carry = 0; i < static_cast<int>(other.z.size()) || carry; ++i) {
- if (i == static_cast<int>(z.size())) {
- z.push_back(0);
- }
- z[i] += carry + (i < static_cast<int>(other.z.size()) ? other.z[i] : 0);
- carry = z[i] >= kBase;
- if (carry) {
- z[i] -= kBase;
- }
- }
- } else if (other != 0 /* prevent infinite loop */) {
- *this -= -other;
- }
- return *this;
- }
- friend Bigint operator+(Bigint a, const Bigint &b) {
- a += b;
- return a;
- }
- Bigint &operator-=(const Bigint &other) {
- if (sign == other.sign) {
- if ((sign == 1 && *this >= other) || (sign == -1 && *this <= other)) {
- for (int i = 0, carry = 0; i < static_cast<int>(other.z.size()) || carry; ++i) {
- z[i] -= carry + (i < static_cast<int>(other.z.size()) ? other.z[i] : 0);
- carry = z[i] < 0;
- if (carry) {
- z[i] += kBase;
- }
- }
- trim();
- } else {
- *this = other - *this;
- this->sign = -this->sign;
- }
- } else {
- *this += -other;
- }
- return *this;
- }
- friend Bigint operator-(Bigint a, const Bigint &b) {
- a -= b;
- return a;
- }
- Bigint &operator*=(int v) {
- if (v < 0) {
- sign = -sign, v = -v;
- }
- for (int i = 0, carry = 0; i < static_cast<int>(z.size()) || carry; ++i) {
- if (i == static_cast<int>(z.size())) {
- z.push_back(0);
- }
- int64_t cur = static_cast<int64_t>(z[i]) * v + carry;
- carry = static_cast<int>(cur / kBase);
- z[i] = static_cast<int>(cur % kBase);
- }
- trim();
- return *this;
- }
- Bigint operator*(int v) const {
- return Bigint(*this) *= v;
- }
- friend std::pair<Bigint, Bigint> divmod(const Bigint &a1, const Bigint &b1) {
- int norm = kBase / (b1.z.back() + 1);
- Bigint a = a1.abs() * norm;
- Bigint b = b1.abs() * norm;
- Bigint q, r;
- q.z.resize(a.z.size());
- for (int i = static_cast<int>(a.z.size()) - 1; i >= 0; i--) {
- r *= kBase;
- r += a.z[i];
- int s1 = b.z.size() < r.z.size() ? r.z[b.z.size()] : 0;
- int s2 = b.z.size() - 1 < r.z.size() ? r.z[b.z.size() - 1] : 0;
- int d = static_cast<int>((static_cast<int64_t>(s1) * kBase + s2) / b.z.back());
- r -= b * d;
- while (r < 0) {
- r += b, --d;
- }
- q.z[i] = d;
- }
- q.sign = a1.sign * b1.sign;
- r.sign = a1.sign;
- q.trim();
- r.trim();
- return {q, r / norm};
- }
- Bigint operator/(const Bigint &v) const {
- return divmod(*this, v).first;
- }
- Bigint operator%(const Bigint &v) const {
- return divmod(*this, v).second;
- }
- Bigint &operator/=(int v) {
- if (v < 0) {
- sign = -sign, v = -v;
- }
- for (int i = static_cast<int>(z.size()) - 1, rem = 0; i >= 0; --i) {
- int64_t cur = z[i] + rem * static_cast<int64_t>(kBase);
- z[i] = static_cast<int>(cur / v);
- rem = static_cast<int>(cur % v);
- }
- trim();
- return *this;
- }
- Bigint operator/(int v) const {
- return Bigint(*this) /= v;
- }
- int operator%(int v) const {
- if (v < 0) {
- v = -v;
- }
- int m = 0;
- for (int i = static_cast<int>(z.size()) - 1; i >= 0; --i) {
- m = static_cast<int>((z[i] + m * static_cast<int64_t>(kBase)) % v);
- }
- return m * sign;
- }
- Bigint &operator*=(const Bigint &v) {
- *this = *this * v;
- return *this;
- }
- Bigint &operator/=(const Bigint &v) {
- *this = *this / v;
- return *this;
- }
- Bigint &operator%=(const Bigint &v) {
- *this = *this % v;
- return *this;
- }
- bool operator<(const Bigint &v) const {
- if (sign != v.sign) {
- return sign < v.sign;
- }
- if (z.size() != v.z.size()) {
- return z.size() * sign < v.z.size() * v.sign;
- }
- for (int i = static_cast<int>(z.size()) - 1; i >= 0; i--) {
- if (z[i] != v.z[i]) {
- return z[i] * sign < v.z[i] * sign;
- }
- }
- return false;
- }
- bool operator>(const Bigint &v) const {
- return v < *this;
- }
- bool operator<=(const Bigint &v) const {
- return !(v < *this);
- }
- bool operator>=(const Bigint &v) const {
- return !(*this < v);
- }
- bool operator==(const Bigint &v) const {
- return sign == v.sign && z == v.z;
- }
- bool operator!=(const Bigint &v) const {
- return !(*this == v);
- }
- void trim() {
- while (!z.empty() && z.back() == 0) {
- z.pop_back();
- }
- if (z.empty()) {
- sign = 1;
- }
- }
- bool isZero() const {
- return z.empty();
- }
- friend Bigint operator-(Bigint v) {
- if (!v.z.empty()) {
- v.sign = -v.sign;
- }
- return v;
- }
- Bigint abs() const {
- return sign == 1 ? *this : -*this;
- }
- void read(const std::string &s) {
- sign = 1;
- z.clear();
- int pos = 0;
- while (pos < static_cast<int>(s.size()) && (s[pos] == '-' || s[pos] == '+')) {
- if (s[pos] == '-') {
- sign = -sign;
- }
- ++pos;
- }
- for (int i = static_cast<int>(s.size()) - 1; i >= pos; i -= kBaseDigits) {
- int x = 0;
- for (int j = std::max(pos, i - kBaseDigits + 1); j <= i; j++) {
- x = x * 10 + s[j] - '0';
- }
- z.push_back(x);
- }
- trim();
- }
- friend std::istream &operator>>(std::istream &stream, Bigint &v) {
- std::string s;
- stream >> s;
- v.read(s);
- return stream;
- }
- friend std::ostream &operator<<(std::ostream &stream, const Bigint &v) {
- if (v.sign == -1) {
- stream << '-';
- }
- stream << (v.z.empty() ? 0 : v.z.back());
- for (int i = static_cast<int>(v.z.size()) - 2; i >= 0; --i) {
- stream << std::setw(kBaseDigits) << std::setfill('0') << v.z[i];
- }
- return stream;
- }
- static std::vector<int> convertBase(const std::vector<int> &a, int old_digits, int new_digits) {
- std::vector<int64_t> p(std::max(old_digits, new_digits) + 1);
- p[0] = 1;
- for (int i = 1; i < static_cast<int>(p.size()); i++) {
- p[i] = p[i - 1] * 10;
- }
- std::vector<int> res;
- int64_t cur = 0;
- int cur_digits = 0;
- for (int v : a) {
- cur += v * p[cur_digits];
- cur_digits += old_digits;
- while (cur_digits >= new_digits) {
- res.push_back(int(cur % p[new_digits]));
- cur /= p[new_digits];
- cur_digits -= new_digits;
- }
- }
- res.push_back(static_cast<int>(cur));
- while (!res.empty() && res.back() == 0) {
- res.pop_back();
- }
- return res;
- }
- Bigint operator*(const Bigint &v) const {
- if (std::min(z.size(), v.z.size()) < 150) {
- return mulSimple(v);
- }
- Bigint res;
- res.sign = sign * v.sign;
- res.z = multiplyBigint(convertBase(z, kBaseDigits, kFftBaseDigits),
- convertBase(v.z, kBaseDigits, kFftBaseDigits), kFftBase);
- res.z = convertBase(res.z, kFftBaseDigits, kBaseDigits);
- res.trim();
- return res;
- }
- Bigint mulSimple(const Bigint &v) const {
- Bigint res;
- res.sign = sign * v.sign;
- res.z.resize(z.size() + v.z.size());
- for (int i = 0; i < static_cast<int>(z.size()); ++i) {
- if (z[i]) {
- for (int j = 0, carry = 0; j < static_cast<int>(v.z.size()) || carry; ++j) {
- int64_t cur = res.z[i + j] +
- static_cast<int64_t>(z[i]) *
- (j < static_cast<int>(v.z.size()) ? v.z[j] : 0) +
- carry;
- carry = static_cast<int>(cur / kBase);
- res.z[i + j] = static_cast<int>(cur % kBase);
- }
- }
- }
- res.trim();
- return res;
- }
- };
- int k_n = 800;
- int n;
- std::vector<Bigint> f;
- std::vector<int> v;
- void precalc() {
- f[std::min(n - 1, k_n - 1)] = 1;
- for (int i = std::min(k_n, n) - 2; i >= 0; i--) {
- f[i] = f[i + 1] * (n - (std::min(k_n, n) - 2 - i));
- }
- }
- int main() {
- std::ios::sync_with_stdio(false);
- std::cin.tie(nullptr);
- std::cin >> n;
- Bigint kek = 1;
- for (int i = 1; i <= 1000; i++) {
- kek *= i;
- }
- Bigint meme = 1;
- int noooo = std::max(n, 1000);
- while (meme < kek) {
- meme *= noooo;
- noooo--;
- }
- k_n = n - noooo + 1;
- f.resize(k_n);
- v.resize(k_n);
- precalc();
- Bigint k;
- std::cin >> k;
- k -= 1;
- for (int i = 0; i + k_n < n; i++) {
- std::cout << 1 << ' ';
- }
- int lol = 0;
- for (int i = std::max(0, n - k_n); i < n; i++) {
- Bigint cnt = f[i - std::max(0, n - k_n)];
- int l = 1, r = i + 1;
- while (l < r) {
- int m = (l + r + 1) / 2;
- if (cnt * (m - 1) <= k) {
- l = m;
- } else {
- r = m - 1;
- }
- }
- k -= cnt * (l - 1);
- v[i - std::max(0, n - k_n)] = l;
- lol++;
- } //
- for (int i = 0; i + 1 < lol; i++) {
- std::cout << v[i] << ' ';
- }
- std::cout << v[lol - 1];
- }
Advertisement
Add Comment
Please, Sign In to add comment