結果

問題 No.696 square1001 and Permutation 5
ユーザー square1001
提出日時 2022-08-20 13:48:48
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 726 ms / 10,000 ms
コード長 18,446 bytes
コンパイル時間 2,036 ms
コンパイル使用メモリ 103,408 KB
実行使用メモリ 30,700 KB
最終ジャッジ日時 2024-10-09 06:42:07
合計ジャッジ時間 5,734 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma GCC optimize("O3")
#ifndef CLASS_MODINT_64321
#define CLASS_MODINT_64321
 
#include <cassert>
#include <cstdint>
 
class modint_64321 {
private:
    static constexpr std::uint64_t mod = std::uint64_t(1) - (std::uint64_t(1) << 32);
    std::uint64_t n;
public:
    modint_64321() noexcept : n(0) {};
    modint_64321(std::uint64_t n_) noexcept : n(n_ < mod ? n_ : n_ - mod) {};
    modint_64321(std::uint32_t n_) noexcept : n(n_) {};
    modint_64321(std::int64_t n_) noexcept : n(n_ >= 0 ? n_ : std::uint64_t(n_) + mod) {};
    modint_64321(std::int32_t n_) noexcept : n(n_ >= 0 ? n_ : std::uint64_t(n_) + mod) {};
    static constexpr std::uint64_t get_mod() noexcept { return mod; }
    std::uint64_t get() const noexcept { return n; }
    bool operator==(const modint_64321& m) const noexcept { return n == m.n; }
    bool operator!=(const modint_64321& m) const noexcept { return n != m.n; }
    modint_64321& operator+=(const modint_64321& m) noexcept { n = (n < mod - m.n ? n + m.n : n + m.n - mod); return *this; }
    modint_64321& operator-=(const modint_64321& m) noexcept { n = (n >= m.n ? n - m.n : n - m.n + mod); return *this; }
#ifdef __SIZEOF_INT128__
    modint_64321& operator*=(const modint_64321& m) noexcept {
        __uint128_t g = __int128_t(n) * m.n;
        std::uint64_t g0 = g & 4294967295;
        std::uint64_t g1 = (g >> 32) & 4294967295;
        std::uint64_t g2 = (g >> 64) & 4294967295;
        std::uint64_t g3 = (g >> 96);
        n = ((g1 + g2) << 32) - (g1 + g2 < 4294967296 ? 0 : mod) + g0 - g2 - g3;
        n = (n < mod ? n : (g1 + g2 != 4294967295 ? n + mod : n - mod));
        return *this;
    }
#else
    modint_64321& operator*=(const modint_64321& m) noexcept {
        std::uint64_t la = n & 4294967295, lb = (n >> 32);
        std::uint64_t ra = m.n & 4294967295, rb = (m.n >> 32);
        std::uint64_t g0 = 0, g1 = 0, g2 = 0, g3 = 0;
        g0 += la * ra; g1 += (g0 >> 32); g0 &= 4294967295;
        g1 += la * rb; g2 += (g1 >> 32); g1 &= 4294967295;
        g1 += lb * ra; g2 += (g1 >> 32); g1 &= 4294967295;
        g2 += lb * rb; g3 += (g2 >> 32); g2 &= 4294967295;
        n = ((g1 + g2) << 32) - (g1 + g2 < 4294967296 ? 0 : mod) + g0 - g2 - g3;
        n = (n < mod ? n : (g1 + g2 != 4294967295 ? n + mod : n - mod));
        return *this;
    }
#endif
    modint_64321 operator+(const modint_64321& m) const noexcept { return modint_64321(*this) += m; }
    modint_64321 operator-(const modint_64321& m) const noexcept { return modint_64321(*this) -= m; }
    modint_64321 operator*(const modint_64321& m) const noexcept { return modint_64321(*this) *= m; }
    modint_64321 inv() const {
        assert(n != 0);
        return pow(mod - 2);
    }
    modint_64321 pow(std::uint64_t b) const noexcept {
        modint_64321 ans(1), m(*this);
        while (b) {
            if (b & 1) ans *= m;
            m *= m;
            b >>= 1;
        }
        return ans;
    }
};
 
#endif // CLASS_MODINT_64321
 
#ifndef CLASS_POLYNOMIAL_NTT_64321
#define CLASS_POLYNOMIAL_NTT_64321
 
#include <vector>
#include <algorithm>
 
class polynomial_ntt_64321 {
public:
    using modulo = modint_64321;
private:
    static constexpr std::uint64_t primroot = 7;
    static constexpr std::uint64_t mod = modulo::get_mod();
public:
    static void fourier_transform(std::vector<modulo>& v) {
        std::vector<modulo> base_pw(33);
        base_pw[32] = modulo(primroot).pow((mod - 1) >> 32);
        for (int i = 31; i >= 0; --i) {
            base_pw[i] = base_pw[i + 1] * base_pw[i + 1];
        }
        for (int i = 32; i >= 0; --i) {
            base_pw[i] *= modulo(-1);
        }
        std::size_t s = v.size();
        for (std::size_t i = (s >> 1); i >= 1; i >>= 1) {
            modulo w(1);
            std::size_t cnt = 0;
            for (std::size_t j = 0; j < s; j += i * 2) {
                for (std::size_t k = j; k < j + i; ++k) {
                    modulo va(v[k]), vb(v[k + i] * w);
                    v[k] = va + vb;
                    v[k + i] = va - vb;
                }
                w *= base_pw[__builtin_ctz(++cnt) + 2];
            }
        }
    }
    static void fourier_transform_inverse(std::vector<modulo>& v) {
        std::vector<modulo> base_pw(33);
        base_pw[32] = modulo(primroot).pow((mod - 1) - ((mod - 1) >> 32));
        for (int i = 31; i >= 0; --i) {
            base_pw[i] = base_pw[i + 1] * base_pw[i + 1];
        }
        for (int i = 32; i >= 0; --i) {
            base_pw[i] *= modulo(-1);
        }
        std::size_t s = v.size();
        for (std::size_t i = 1; i < s; i <<= 1) {
            modulo w(1);
            std::size_t cnt = 0;
            for (std::size_t j = 0; j < s; j += i * 2) {
                for (std::size_t k = j; k < j + i; ++k) {
                    modulo va(v[k]), vb(v[k + i]);
                    v[k] = va + vb;
                    v[k + i] = (va - vb) * w;
                }
                w *= base_pw[__builtin_ctz(++cnt) + 2];
            }
        }
        modulo powinv = modulo(s).inv();
        for (std::size_t i = 0; i < s; ++i) {
            v[i] *= powinv;
        }
    }
    static std::vector<modulo> convolve(std::vector<modulo> v1, std::vector<modulo> v2) {
        if (v1.empty() || v2.empty()) {
            return std::vector<modulo>();
        }
        if (v1.size() <= 64 || v2.size() <= 64) {
            std::vector<modulo> ans_naive(v1.size() + v2.size() - 1);
            for (std::size_t i = 0; i < v1.size(); ++i) {
                for (std::size_t j = 0; j < v2.size(); ++j) {
                    ans_naive[i + j] += v1[i] * v2[j];
                }
            }
            return ans_naive;
        }
        if (v1.size() < v2.size()) {
            swap(v1, v2);
        }
        std::size_t fsize = v1.size() + v2.size() - 1;
        std::size_t step = v2.size();
        while (step & (step - 1)) {
            step += step & (-step); // step to become minimum 2^k >= v2.size()
        }
        v1.resize((v1.size() + step - 1) / step * step); // change v1.size() to multiple of step
        v2.resize(step * 2);
        std::vector<modulo> ans(fsize);
        std::vector<modulo> pv1(step * 2);
        fourier_transform(v2);
        for (std::size_t i = 0; i < v1.size(); i += step) {
            std::copy(v1.begin() + i, v1.begin() + i + step, pv1.begin());
            std::fill(pv1.begin() + step, pv1.end(), modulo(0));
            fourier_transform(pv1);
            for (std::size_t j = 0; j < step * 2; ++j) {
                pv1[j] *= v2[j];
            }
            fourier_transform_inverse(pv1);
            for (std::size_t j = 0; j < step * 2 && i + j < fsize; ++j) {
                ans[j + i] += pv1[j];
            }
        }
        return ans;
    }
};
 
#endif // CLASS_POLYNOMIAL_NTT_64321
 
#ifndef CLASS_BASICINT
#define CLASS_BASICINT
 
#include <vector>
#include <cassert>
#include <cstdint>
#include <algorithm>
 
template<std::uint32_t base>
class basic_int {
    // 2 <= base < max(base_type)^(2/3) = 2,642,245
protected:
    using base_type = std::uint32_t; // base type
    using base_type_d = std::uint64_t; // double of base type
    std::size_t capacity;
    std::vector<base_type> digit;
    void resize(std::size_t capacity_) {
        if (capacity != capacity_) {
            assert(capacity_ >= 1);
            capacity = capacity_;
            digit.resize(capacity_);
        }
    }
    void minimize() {
        std::size_t d = digits();
        while (d & (d - 1)) {
            d += d & (-d);
        }
        resize(d);
    }
    std::size_t digits() const {
        for (std::size_t i = capacity - 1; i >= 1; --i) {
            if (digit[i] != 0) {
                return i + 1;
            }
        }
        return 1;
    }
public:
    // ----- #1. Costructors ----- //
    explicit basic_int() : capacity(1), digit(1, base_type(0)) {};
    explicit basic_int(std::vector<base_type> digit_) : digit(digit_) {
        assert(!digit.empty());
        for (base_type i : digit) {
            assert(0 <= i && i < base);
        }
        capacity = 1;
        while (capacity < digit.size()) {
            capacity <<= 1;
        }
        digit.resize(capacity, 0);
    };
 
    // ----- #2. Comparing Operators ----- //
    bool operator==(const basic_int& b) const noexcept {
        return digit == b.digit;
    }
    bool operator!=(const basic_int& b) const noexcept {
        return digit != b.digit;
    }
    bool operator<(const basic_int& b) const noexcept {
        if (capacity != b.capacity) {
            return capacity < b.capacity;
        }
        for (std::size_t i = capacity - 1; i >= 1; --i) {
            if (digit[i] != b.digit[i]) {
                return digit[i] < b.digit[i];
            }
        }
        return digit[0] < b.digit[0];
    }
    bool operator>(const basic_int& b) const noexcept {
        if (capacity != b.capacity) {
            return capacity > b.capacity;
        }
        for (std::size_t i = capacity - 1; i >= 1; --i) {
            if (digit[i] != b.digit[i]) {
                return digit[i] > b.digit[i];
            }
        }
        return digit[0] > b.digit[0];
    }
    bool operator<=(const basic_int& b) const noexcept {
        return basic_int(*this) < b || basic_int(*this) == b;
    }
    bool operator>=(const basic_int& b) const noexcept {
        return basic_int(*this) > b || basic_int(*this) == b;
    }
 
    // ----- #3. Shifting ----- //
    basic_int& operator<<=(std::size_t s) noexcept {
        std::size_t d = digits();
        if (d + s > capacity) {
            std::size_t nxtcap = d + s;
            while (nxtcap & (nxtcap - 1)) {
                nxtcap += nxtcap & (-nxtcap);
            }
            resize(nxtcap);
        }
        for (std::size_t i = d - 1; i != std::size_t(-1); --i) {
            digit[i + s] = digit[i];
        }
        std::fill(digit.begin(), digit.begin() + s, 0);
        return *this;
    }
    basic_int& operator>>=(std::size_t s) noexcept {
        std::size_t d = digits();
        if (d <= s) {
            (*this) = basic_int();
        }
        else {
            for (std::size_t i = 0; i < d - s; ++i) {
                digit[i] = digit[i + s];
            }
            std::fill(digit.begin() + d - s, digit.begin() + d, 0);
            minimize();
        }
        return *this;
    }
 
    // ----- #4. Addition ----- //
    basic_int& operator+=(const basic_int& b) {
        resize(std::max(capacity, b.capacity));
        bool carry = false;
        for (std::uint32_t i = 0; i < b.capacity; ++i) {
            digit[i] += b.digit[i] + (carry ? 1 : 0);
            carry = (digit[i] >= base);
            if (carry) digit[i] -= base;
        }
        for (std::uint32_t i = b.capacity; i < capacity; ++i) {
            digit[i] += (carry ? 1 : 0);
            carry = (digit[i] >= base);
            if (carry) digit[i] -= base;
        }
        if (carry) {
            resize(capacity << 1);
            digit[capacity >> 1] = 1;
        }
        return *this;
    }
 
    // ----- #5. Subtraction ----- //
    basic_int& operator-=(const basic_int& b) {
        bool carry = false;
        for (std::uint32_t i = 0; i < b.capacity; ++i) {
            digit[i] += base - b.digit[i] - (carry ? 1 : 0);
            carry = (digit[i] < base);
            if (!carry) digit[i] -= base;
        }
        for (std::uint32_t i = b.capacity; i < capacity; ++i) {
            digit[i] += base - (carry ? 1 : 0);
            carry = (digit[i] < base);
            if (!carry) digit[i] -= base;
        }
        // assert(!carry) // noexcept
        minimize();
        return *this;
    }
 
    // ----- #6. Multiplication ----- //
    basic_int& operator*=(const basic_int& b) {
        using ntt = polynomial_ntt_64321;
        std::size_t nxtcap = std::max(capacity, b.capacity) * 2;
        std::vector<ntt::modulo> nxtdigit = ntt::convolve(std::vector<ntt::modulo>(digit.begin(), digit.end()), std::vector<ntt::modulo>(b.digit
            .begin(), b.digit.end()));
        nxtdigit.resize(nxtcap);
        capacity = nxtcap;
        digit = std::vector<std::uint32_t>(capacity, 0);
        std::uint64_t carry = 0;
        for (std::uint32_t i = 0; i < capacity; ++i) {
            std::uint64_t nxt = nxtdigit[i].get() + carry;
            carry = nxt / base;
            digit[i] = nxt - carry * base;
        }
        minimize();
        return *this;
    }
 
    // ----- #7. Division ----- //
    basic_int& operator/=(const basic_int& b) {
        assert(b != basic_int());
        if ((*this) < b) {
            (*this) = basic_int();
        }
        else {
            std::size_t digit_a = digits();
            std::size_t digit_b = b.digits();
            std::size_t req_precis = digit_a - digit_b + 2;
            std::size_t set_precis = 1;
            while (set_precis < req_precis) set_precis <<= 1;
            // Find the inverse!
            std::uint64_t gen = (digit_b == 1 ? std::uint64_t(b.digit[0]) * base : std::uint64_t(b.digit[digit_b - 1]) * base + b.digit[digit_b - 2]
                );
            std::uint64_t gen_inv = std::uint64_t(base) * base * base / (gen + 1);
            std::size_t current_precis = 2;
            basic_int inv({ std::uint32_t(gen_inv % base), std::uint32_t(gen_inv / base) });
            while (current_precis < set_precis) {
                std::size_t digit_nb = std::min(digit_b, current_precis * 2);
                basic_int nb = (digit_b == digit_nb ? b : b >> (digit_b - digit_nb));
                inv = (((basic_int({ 2 }) << (current_precis + digit_nb - 1)) - inv * nb - basic_int({ 1 })) * inv) >> (digit_nb - 1);
                current_precis *= 2;
            }
            while (true) {
                basic_int next_inv = (((basic_int({ 2 }) << (current_precis + digit_b - 1)) - inv * b - basic_int({ 1 })) * inv) >> (set_precis + 
                    digit_b - 1);
                if (inv == next_inv) break;
                inv = next_inv;
            }
            basic_int val = (basic_int(*this) * inv) >> (set_precis + digit_b - 1);
            while (b * (val + basic_int({ 1 })) <= (*this)) {
                val += basic_int({ 1 });
            }
            (*this) = val;
        }
        return *this;
    }
 
    // ----- #8. Operators ----- //
    basic_int operator<<(std::size_t s) const { return basic_int(*this) <<= s; }
    basic_int operator>>(std::size_t s) const { return basic_int(*this) >>= s; }
    basic_int operator+(const basic_int& b) const { return basic_int(*this) += b; }
    basic_int operator-(const basic_int& b) const { return basic_int(*this) -= b; }
    basic_int operator*(const basic_int& b) const { return basic_int(*this) *= b; }
    basic_int operator/(const basic_int& b) const { return basic_int(*this) /= b; }
};
 
#endif // CLASS_BASICINT
 
#ifndef CLASS_BIGINT
#define CLASS_BIGINT
 
#include <string>
#include <iostream>
 
// (digit / base_digit) * base_number^2 <= 2^64 - 2^32 + 1 = 18446744069414584321
// (digit / base_digit) < min(2^27, 2^26) = 67108864
// ---> max_digit = min(92233720, 335544320) = 92233720
 
constexpr std::size_t base_digit = 6;
constexpr std::uint32_t base_number = 1000000;
 
class bigint : private basic_int<base_number> {
private:
    bool sign; // positive/zero = false, negative = true
    bool is_number(std::string str) {
        if(str.empty() || str == "-" || !(('0' <= str[0] && str[0] <= '9') || str[0] == '-')) {
            return false;
        }
        for(std::uint64_t i = 1; i < str.size(); ++i) {
            if(!('0' <= str[i] && str[i] <= '9')) {
                return false;
            }
        }
        return true;
    }
    std::vector<std::uint32_t> to_basic_expression(std::uint64_t x) {
        std::vector<std::uint32_t> res;
        do {
            res.push_back(x % base_number);
            x /= base_number;
        } while(x != 0);
        return res;
    }
public:
    // ----- #1. Constructors / String Functions ----- //
    bigint() : basic_int(), sign(false) {};
    bigint(std::int64_t x) : basic_int(to_basic_expression(x >= 0 ? x : -x)), sign(x < 0) {};
    bigint(const std::string& str) {
        assert(is_number(str));
        sign = (str[0] == '-');
        std::size_t initial = (sign ? 1 : 0);
        while(initial + 1 != str.size() && str[initial] == '0') {
            ++initial;
        }
        std::size_t str_digits = str.size() - initial;
        capacity = 1;
        while(capacity * base_digit < str_digits) {
            capacity *= 2;
        }
        digit = std::vector<std::uint32_t>(capacity, 0);
        for(std::size_t i = 0; (i + 1) * base_digit < str_digits; ++i) {
            digit[i] = std::stoi(str.substr(str.size() - i * base_digit - base_digit, base_digit));
        }
        digit[(str_digits - 1) / base_digit] = std::stoi(str.substr(initial, (str.size() - (str_digits - 1) / base_digit * base_digit) - initial));
    }
    std::string to_string() const {
        std::size_t d = digits();
        std::string res = (sign ? "-" : "") + std::to_string(digit[d - 1]);
        for(std::size_t i = d - 2; i != std::size_t(-1); --i) {
            std::string digit_str = std::to_string(digit[i]);
            res += std::string(base_digit - digit_str.size(), '0') + digit_str;
        }
        return res;
    }
 
    // ----- #2. Operators ----- //
    bool operator==(const bigint& b) const noexcept { return sign == b.sign && basic_int::operator==(b); }
    bool operator!=(const bigint& b) const noexcept { return sign != b.sign || basic_int::operator!=(b); }
    bool operator<(const bigint& b) const noexcept { return sign != b.sign ? sign : basic_int::operator<(b); }
    bool operator>(const bigint& b) const noexcept { return sign != b.sign ? !sign : basic_int::operator>(b); }
    bool operator<=(const bigint& b) const noexcept { return sign != b.sign ? sign : basic_int::operator<=(b); }
    bool operator>=(const bigint& b) const noexcept { return sign != b.sign ? !sign : basic_int::operator>=(b); }
    bigint& operator+=(const bigint& b) {
        if(sign == b.sign) {
            basic_int::operator+=(b);
        }
        else if(basic_int(*this) >= basic_int(b)) {
            basic_int::operator-=(b);
            if(sign && basic_int(*this) == basic_int()) sign = false;
        }
        else {
            sign = !sign;
            (*this) = b - (*this);
        }
        return *this;
    }
    bigint& operator-=(const bigint& b) {
        if(sign != b.sign) {
            basic_int::operator+=(b);
        }
        else if(basic_int(*this) >= basic_int(b)) {
            basic_int::operator-=(b);
            if(sign && basic_int(*this) == basic_int()) sign = false;
        }
        else {
            sign = !sign;
            (*this) += b;
            sign = !sign;
        }
        return *this;
    }
    bigint& operator*=(const bigint& b) {
        basic_int::operator*=(b);
        if(b.sign) sign = !sign;
        if(sign && basic_int(*this) == basic_int()) sign = false;
        return *this;
    }
    bigint& operator/=(const bigint& b) {
        basic_int::operator/=(b);
        if(b.sign) sign = !sign;
        if(sign && basic_int(*this) == basic_int()) sign = false;
        return *this;
    }
    bigint operator%=(const bigint& b) {
        bigint itself(*this);
        (*this) = itself - itself / b * b;
        return *this;
    }
    bigint operator+(const bigint& b) const { return bigint(*this) += b; }
    bigint operator-(const bigint& b) const { return bigint(*this) -= b; }
    bigint operator*(const bigint& b) const { return bigint(*this) *= b; }
    bigint operator/(const bigint& b) const { return bigint(*this) /= b; }
    bigint operator%(const bigint& b) const { return bigint(*this) %= b; }
    friend std::istream& operator>>(std::istream& is, bigint& x) { std::string s; is >> s; x = bigint(s); return is; }
    friend std::ostream& operator<<(std::ostream& os, const bigint& x) { os << x.to_string(); return os; }
};
 
#endif // CLASS_BIGINT
#include <vector>
#include <iostream>
using namespace std;
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> p(n), bit(n);
    vector<bigint> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> p[i];
    for (int i = n - 1; i >= 0; i--) {
        int x = 0;
        for (int j = p[i] - 1; j >= 1; j -= j & (-j)) x += bit[j];
        for (int j = p[i]; j < n; j += j & (-j)) bit[j]++;
        a[n - i - 1] = x;
        b[i] = i + 1;
    }
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j + i < n; j += 2 * i) {
            a[j] = a[j] + b[j] * a[j + i];
            b[j] = b[j] * b[j + i];
        }
    }
    cout << a[0] + 1 << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0