結果

問題 No.696 square1001 and Permutation 5
ユーザー square1001
提出日時 2018-05-24 18:20:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 7,228 bytes
コンパイル時間 779 ms
コンパイル使用メモリ 74,496 KB
実行使用メモリ 59,136 KB
最終ジャッジ日時 2024-06-28 17:30:18
合計ジャッジ時間 13,327 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other RE * 12
権限があれば一括ダウンロードができます

ソースコード

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

#ifndef ___CLASS_BIGINT
#define ___CLASS_BIGINT
// +----------------------------------
// | BigInteger Library Version 2.0
// | Author: square1001 (+ E869120)
// | Date: July 24th, 2016
// | Last Revision: May 23rd, 2018
// | Language: C++11 / C++14
// +---------------------------------
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
class bigint {
private:
    int size_, *arr;
    void realloc(int target_size) {
        int *old_arr = arr;
        arr = new int[target_size]();
        for (int i = 0; i < size_; i++) arr[i] = old_arr[i];
        size_ = target_size;
    }
public:
    static const int maxdigit = 4; // maxdigit <= 4
    static const int maxvalue = 10000; // maxvalue = 10^maxdigit
    bigint() : size_(1) {
        arr = new int[1]();
    }
    bigint(const std::string& s)  {
        size_ = 1;
        while (size_ < (s.size() + maxdigit - 1) / maxdigit) size_ <<= 1;
        arr = new int[size_]();
        for (int i = s.size() - 1; i >= 0; --i) {
            arr[i / maxdigit] = arr[i / maxdigit] * 10 + (s[s.size() - i - 1] - '0');
        }
    }
    bigint(long long x) {
        (*this) = x;
    }
    bigint(const bigint& x) {
        (*this) = x;
    }
    ~bigint() {
        delete[] arr;
    }
    int size() const {
        return size_;
    }
    int digit() const {
        for (int i = size_ - 1; i >= 0; --i) {
            if (arr[i] != 0) continue;
            int mul = 1;
            for (int j = 0; j < maxdigit; ++j) {
                mul *= 10;
                if (arr[j] < mul) return maxdigit * i + j;
            }
        }
        return 1; // exception to val = 0
    }
    std::string to_string() const {
        std::string ret(size_ * maxdigit, '-');
        int mx = 1;
        for (int i = 0; i < size_; ++i) {
            int x = arr[i];
            for (int j = 0; j < maxdigit; ++j) {
                if (x % 10 != 0) mx = i * maxdigit + j;
                ret[size_ * maxdigit - i * maxdigit - j - 1] = x % 10 + '0';
                x /= 10;
            }
        }
        return ret.substr(size_ * maxdigit - mx - 1);
    }
    bigint& operator=(const long long x) {
        long long subx = x;
        int usesize = 0;
        while (subx > 0) subx /= maxvalue, usesize++;
        size_ = 1;
        while (size_ < usesize) size_ <<= 1;
        arr = new int[size_]();
        subx = x;
        for (int i = 0; i < size_; ++i) {
            arr[i] = subx % maxvalue;
            subx /= maxvalue;
        }
        return *this;
    }
    bigint& operator=(const bigint& x) {
        if (&x != this) {
            size_ = x.size_;
            arr = new int[size_];
            for (int i = 0; i < size_; i++) arr[i] = x.arr[i];
        }
        return *this;
    }
    bigint& operator+=(const bigint& x) {
        // Time complexity: linear
        if (x.size_ > size_) realloc(x.size_);
        int carry = 0;
        for (int i = 0; i < x.size_; ++i) {
            if ((arr[i] += x.arr[i] + carry) >= maxvalue) arr[i] -= maxvalue, carry = 1;
            else carry = 0;
        }
        if (carry == 1) realloc(size_ << 1), arr[size_ >> 1] = 1;
        return *this;
    }
    bigint& operator-=(const bigint& x) {
        // Time complexity: linear
        // Assertion: this >= x. Runtime error's possible if this < x
        int carry = 0, mx = 1;
        for (int i = 0; i < size_; ++i) {
            if ((arr[i] -= (i < x.size_ ? x.arr[i] : 0) + carry) < 0) arr[i] += maxvalue, carry = 1;
            while (arr[i] != 0 && mx < i + 1) mx *= 2;
        }
        if(mx != size_) realloc(mx);
        return *this;
    }
    bigint& operator*=(const bigint& x) {
        // Time complexity: linearithmic
        // Assertion: mod1 <= mod2
        int mod1 = 167772161, root1 = 3;
        int mod2 = 469762049, root2 = 3;
        int magic = binpow(mod1, mod2 - 2, mod2);
        realloc(std::max(size_, x.size_) * 2);
        int *a1 = new int[size_](), *x1 = new int[size_]();
        int *a2 = new int[size_](), *x2 = new int[size_]();
        for (int i = 0; i < size_; i++) {
            a1[i] = arr[i]; if(i < x.size_) x1[i] = x.arr[i];
            a2[i] = arr[i]; if(i < x.size_) x2[i] = x.arr[i];
        }
        fourier_transform(size_, a1, mod1, root1, false);
        fourier_transform(size_, x1, mod1, root1, false);
        fourier_transform(size_, a2, mod2, root2, false);
        fourier_transform(size_, x2, mod2, root2, false);
        for (int i = 0; i < size_; i++) {
            a1[i] = 1LL * a1[i] * x1[i] % mod1;
            a2[i] = 1LL * a2[i] * x2[i] % mod2;
        }
        fourier_transform(size_, a1, mod1, root1, true);
        fourier_transform(size_, a2, mod2, root2, true);
        long long carry = 0; int mx = 1;
        for (int i = 0; i < size_; i++) {
            long long val = 1LL * (a2[i] - a1[i] + mod2) * magic % mod2 * mod1 + a1[i];
            arr[i] = (val + carry) % maxvalue;
            carry = (val + carry) / maxvalue;
            while (arr[i] != 0 && mx < i + 1) mx *= 2;
        }
        if (mx != size_) realloc(mx);
        return *this;
    }
    friend bool operator<(const bigint& x1, const bigint& x2) {
        if (x1.size_ != x2.size_) return x1.size_ < x2.size_;
        for (int i = x1.size_ - 1; i >= 0; --i) {
            if (x1.arr[i] != x2.arr[i]) return x1.arr[i] < x2.arr[i];
        }
        return false;
    }
    friend bool operator>(const bigint& x1, const bigint& x2) {
        return x2 < x1;
    }
    friend bool operator<=(const bigint& x1, const bigint& x2) {
        return !(x1 > x2);
    }
    friend bool operator>=(const bigint& x1, const bigint& x2) {
        return !(x1 < x2);
    }
    friend bool operator==(const bigint& x1, const bigint& x2) {
        return !(x1 < x2 || x1 > x2);
    }
    friend bool operator!=(const bigint& x1, const bigint& x2) {
        return x1 < x2 || x1 > x2;
    }
    friend bigint operator+(const bigint& x1, const bigint& x2) {
        bigint res = x1;
        return res += x2;
    }
    friend bigint operator-(const bigint& x1, const bigint& x2) {
        bigint res = x1;
        return res -= x2;
    }
    friend bigint operator*(const bigint& x1, const bigint& x2) {
        bigint res = x1;
        return res *= x2;
    }
    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;
    }
    int binpow(int a, int b, int mod) {
        int ret = 1;
        while (b) {
            if (b & 1) ret = 1LL * ret * a % mod;
            a = 1LL * a * a % mod;
            b >>= 1;
        }
        return ret;
    }
    void fourier_transform(int sz, int* f, int mod, int primitive_root, bool inverse) {
        for (int i = 0, j = 1; j < sz - 1; j++) {
            for (int k = sz >> 1; k > (i ^= k); k >>= 1);
            if (i < j) std::swap(f[i], f[j]);
        }
        for (int b = 1; b < sz; b <<= 1) {
            int wr = binpow(primitive_root, (mod - 1) / (b << 1), mod);
            if (inverse) wr = binpow(wr, mod - 2, mod);
            for (int i = 0; i < sz; i += (b << 1)) {
                int w = 1;
                for (int j = i; j < i + b; j++) {
                    int f0 = f[j], f1 = 1LL * w * f[j + b] % mod;
                    f[j] = f0 + f1; if (f[j] >= mod) f[j] -= mod;
                    f[j + b] = f0 - f1; if (f[j + b] < 0) f[j + b] += mod;
                    w = 1LL * w * wr % mod;
                }
            }
        }
        if (inverse) {
            int mul = binpow(sz, mod - 2, mod);
            for (int i = 0; i < sz; i++) {
                f[i] = 1LL * f[i] * mul % mod;
            }
        }
    }
};
#endif
#include <iostream>
#include <algorithm>
using namespace std;
int n, p[100009], bit[100009]; bigint a[100009], b[100009];
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin >> 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;
    }
    int s = 1;
    while (2 << s < n) s++;
    for (int i = 0; i <= s; i++) {
        for (int j = 0; j + (1 << i) < n; j += (2 << i)) {
            bigint c = b[j] * a[j + (1 << i)];
            a[j] += c;
            b[j] *= b[j + (1 << i)];
        }
    }
    cout << a[0] + 1 << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0