結果
問題 | No.696 square1001 and Permutation 5 |
ユーザー | square1001 |
提出日時 | 2018-05-21 21:48:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4,606 ms / 10,000 ms |
コード長 | 10,421 bytes |
コンパイル時間 | 1,502 ms |
コンパイル使用メモリ | 101,276 KB |
実行使用メモリ | 39,904 KB |
最終ジャッジ日時 | 2024-06-30 07:08:37 |
合計ジャッジ時間 | 15,540 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2,429 ms
39,600 KB |
testcase_01 | AC | 18 ms
16,000 KB |
testcase_02 | AC | 17 ms
16,120 KB |
testcase_03 | AC | 17 ms
16,256 KB |
testcase_04 | AC | 20 ms
16,256 KB |
testcase_05 | AC | 23 ms
16,384 KB |
testcase_06 | AC | 32 ms
16,612 KB |
testcase_07 | AC | 50 ms
17,120 KB |
testcase_08 | AC | 214 ms
19,352 KB |
testcase_09 | AC | 941 ms
27,112 KB |
testcase_10 | AC | 2,401 ms
39,904 KB |
testcase_11 | AC | 4,606 ms
32,932 KB |
testcase_12 | AC | 18 ms
16,096 KB |
testcase_13 | AC | 17 ms
15,988 KB |
ソースコード
// +----------------------------------// | BigInteger Library Version 1.1// | Author: square1001, E869120// | Date: July 24th, 2016// | Language: C++11 / C++14// +---------------------------------#ifndef ___Class_BasicInteger#define ___Class_BasicInteger// ------ Includes ------ //#include <string>#include <vector>#include <cassert>#include <cstring>#include <complex>#include <iostream>#include <algorithm>// ------ BasicInteger ------ //class BasicInteger {private:// ------ Variable ------ //int size_;std::vector<int> v;// ------ Private Function ------ //void resize(int size__) {size_ = size__;v.resize(size_, 0);}int digit() {int digit = 1;for (int i = size_ - 1; i >= 1; i--) {if (v[i] != 0) {digit = i + 1;break;}}return digit;}void revalue() {int r = digit();while (size_ >= r * 2) size_ >>= 1;v.resize(size_);}public:// ------ Constants ------ //static const int maxdigit = 4; // maxdigit <= 4static const int maxvalue = 10000; // maxvalue = pow(10, maxdigit)// ------ Constructor ------ //BasicInteger() {size_ = 1;v.resize(size_, 0);}BasicInteger(const std::string &b) {std::string s = b;int r = (s.size() + maxdigit - 1) / maxdigit;size_ = 1;while (size_ < r) size_ <<= 1;v.resize(size_);std::reverse(s.begin(), s.end());int val = 0, cnt = 0, t = 0, p = 1;for (char c : s) {val += (c - 48) * p; p *= 10;if (++cnt == maxdigit) {v[t++] = val;val = 0, cnt = 0, p = 1;}}if (cnt > 0) v[t] = val;}BasicInteger(long long x) {assert(x >= 0);(*this) = x;}BasicInteger(const BasicInteger& b) {size_ = b.size_;v = b.v;}// ------ Functions ------ //int size() const {return size_;}int digit() const {for (int i = size_ - 1; i >= 1; i--) {if (v[i] > 0) return i + 1;}return 1;}std::string to_string() const {std::string ret = "";for (int i = size_ - 1; i >= 0; i--) {std::string t = std::to_string(v[i]);while (t.size() < BasicInteger::maxdigit) t = "0" + t;ret += t;}int r = 0;while (r < size_ * 4 && ret[r] == '0') r++;if (r == size_ * 4) return "0";return ret.substr(r, size_ * 4);}// ------ Basic Operators ------ //BasicInteger& operator=(const long long x) {(*this) = BasicInteger(std::to_string(x));return (*this);}BasicInteger& operator=(const BasicInteger& b) {if (&b != this) {size_ = b.size_;v = b.v;}return (*this);}// ------ Comparision Operators ------ //friend bool operator==(const BasicInteger& b1, const BasicInteger& b2) {return b1.v == b2.v;}friend bool operator!=(const BasicInteger& b1, const BasicInteger& b2) {return b1.v != b2.v;}friend bool operator<(const BasicInteger& b1, const BasicInteger& b2) {if (b1.size_ != b2.size_) return b1.size_ < b2.size_;int n = b1.size_;for (int i = n - 1; i >= 0; i--) {if (b1.v[i] != b2.v[i]) return b1.v[i] < b2.v[i];}return false;}friend bool operator>(const BasicInteger& b1, const BasicInteger& b2) {return b2 < b1;}friend bool operator<=(const BasicInteger& b1, const BasicInteger& b2) {return !(b1 > b2);}friend bool operator>=(const BasicInteger& b1, const BasicInteger& b2) {return !(b1 < b2);}// ------ Addition Operator ------ //friend BasicInteger operator+(const BasicInteger& b1, const BasicInteger& b2) {BasicInteger ret(b1);int n = std::max(b1.size_, b2.size_);ret.resize(n);for (int i = 0; i < b2.size_; i++) ret.v[i] += b2.v[i];for (int i = 0; i < n - 1; i++) {if (ret.v[i] >= BasicInteger::maxvalue) {ret.v[i] -= BasicInteger::maxvalue;ret.v[i + 1]++;}}if (ret.v[n - 1] >= BasicInteger::maxvalue) {ret.resize(n << 1);ret.v[n - 1] -= BasicInteger::maxvalue;ret.v[n] = 1;}return ret;}// ------ Subtraction ------ //friend BasicInteger operator-(const BasicInteger& b1, const BasicInteger& b2) {assert(b1 >= b2);BasicInteger ret(b1);for (int i = 0; i < b2.size_; i++) ret.v[i] -= b2.v[i];for (int i = 0; i < ret.size_; i++) {if (ret.v[i] < 0) {ret.v[i] += BasicInteger::maxvalue;ret.v[i + 1]--;}}ret.revalue();return ret;}// ------ Multiplication ------ //friend BasicInteger operator*(const BasicInteger& b1, const BasicInteger& b2) {BasicInteger ret;BasicInteger b3(b1 < b2 ? b2 : b1); // largeBasicInteger b4(b1 < b2 ? b1 : b2); // smallint d1 = b3.size_, d2 = b4.size_;ret.resize(d1 << 1);for (int i = 0; i < d1; i += d2) {std::vector<int> sub(b3.v.begin() + i, b3.v.begin() + i + d2);std::vector<int> res;if (d1 <= 8192) res = BasicInteger::FastFourierTransform(sub, b4.v);else res = BasicInteger::NumberTheoreticConvolution(sub, b4.v);for (int j = 0; j < (d2 << 1); j++) {ret.v[j + i] += res[j];if (ret.v[j + i] >= BasicInteger::maxvalue) {ret.v[j + i] -= BasicInteger::maxvalue;ret.v[j + i + 1]++;}}}ret.revalue();return ret;}// ------ Normal Multiplication ------ //inline static std::vector<int> NormalMul(const std::vector<int>& b1, const std::vector<int>& b2) {int n = b1.size(); // n <= 2^30, b1 and b2 is the same size!std::vector<long long> ret(n << 1);for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {ret[i + j] += 1LL * b1[i] * b2[j];}}for (int i = 0; i < (n << 1) - 1; i++) {ret[i + 1] += ret[i] / BasicInteger::maxvalue;ret[i] %= BasicInteger::maxvalue;}std::vector<int> res(ret.begin(), ret.end());return res;}// ------ Fast Fourier Transform ------ //inline static void DiscreteFourierTransform(std::vector<std::complex<double> > &f, bool rev = false) {int n = f.size(); // n <= 8192const double pi = acos(-1.0);for (int i = 0, j = 1; j < n - 1; j++) {for (int k = n >> 1; k >(i ^= k); k >>= 1);if (i > j) swap(f[i], f[j]);}for (int b = 2; b <= n; b <<= 1) {std::complex<double> wr = std::polar(1.0, (rev ? -2.0 : 2.0) * pi / b);for (int i = 0; i < n; i += b) {std::complex<double> w(1.0, 0.0);for (int j = 0; j < b >> 1; j++) {std::complex<double> f0 = f[i + j], f1 = w * f[i + j + (b >> 1)];f[i + j] = f0 + f1;f[i + j + (b >> 1)] = f0 - f1;w *= wr;}}}if (rev) {double mul = 1.0 / n;for (int i = 0; i < n; i++) f[i] *= mul;}}inline static std::vector<int> FastFourierTransform(std::vector<int> b1, std::vector<int> b2) {int n = b1.size() * 2; // b1 and b2 is the same size!std::vector<std::complex<double> > f0(n), f1(n);for (int i = 0; i < n >> 1; i++) {f0[i] = b1[i];f1[i] = b2[i];}DiscreteFourierTransform(f0);DiscreteFourierTransform(f1);for (int i = 0; i < n; i++) f0[i] *= f1[i];DiscreteFourierTransform(f0, true);std::vector<long long> res(n);for (int i = 0; i < n; i++) {res[i] = (long long)(f0[i].real() + 0.5);}for (int i = 0; i < n - 1; i++) {res[i + 1] += res[i] / BasicInteger::maxvalue;res[i] %= BasicInteger::maxvalue;}std::vector<int> ret(res.begin(), res.end());return ret;}// ------ Number Theoretic Transform ------ //inline static int modpow(int a, int b, int m) {int ret = 1;for (int i = 30; i >= 0; i--) {ret = 1LL * ret * ret % m;if (b & (1 << i)) ret = 1LL * ret * a % m;}return ret;}inline static void NumberTheoreticTransform(std::vector<int> &f, int mod, int root, bool rev = false) {int n = f.size();for (int i = 0, j = 1; j < n - 1; j++) {for (int k = n >> 1; k >(i ^= k); k >>= 1);if (i < j) std::swap(f[i], f[j]);}for (int b = 1; b < n; b <<= 1) {int wr = modpow(root, (mod - 1) / (b << 1), mod);if (rev) wr = modpow(wr, mod - 2, mod);for (int i = 0; i < n; 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 (rev) {int mul = modpow(n, mod - 2, mod);for (int i = 0; i < n; i++) {f[i] = 1LL * f[i] * mul % mod;}}}inline static std::vector<int> NumberTheoreticModularConvolution(std::vector<int> f0, std::vector<int> f1, int mod, int root) {int n = f0.size() * 2; // f0 and f1 is the same size!f0.resize(n);f1.resize(n);NumberTheoreticTransform(f0, mod, root);NumberTheoreticTransform(f1, mod, root);for (int i = 0; i < n; i++) f0[i] = 1LL * f0[i] * f1[i] % mod;NumberTheoreticTransform(f0, mod, root, true);return f0;}inline static std::vector<int> NumberTheoreticConvolution(std::vector<int> b1, std::vector<int> b2) {int n = b1.size() * 2; // b1 and b2 is the same size!int mod1 = 469762049, r1 = 3;int mod2 = 754974721, r2 = 11;std::vector<int> f0 = NumberTheoreticModularConvolution(b1, b2, mod1, r1);std::vector<int> f1 = NumberTheoreticModularConvolution(b1, b2, mod2, r2);int magic = modpow(mod1, mod2 - 2, mod2);std::vector<long long> res(n);for (int i = 0; i < n; i++) {res[i] = 1LL * (f1[i] - f0[i] + mod2) * magic % mod2 * mod1 + f0[i];}for (int i = 0; i < n - 1; i++) {res[i + 1] += res[i] / BasicInteger::maxvalue;res[i] %= BasicInteger::maxvalue;}std::vector<int> ret(res.begin(), res.end());return ret;}// ------ In / Out Operator ------ //friend std::istream& operator >> (std::istream& is, BasicInteger& b) {std::string res;is >> res;b = BasicInteger(res);return is;}friend std::ostream& operator<<(std::ostream& os, const BasicInteger& b) {os << b.to_string();return os;}};#endif#include <iostream>#include <algorithm>using namespace std;int n, p[100009], bit[100009]; BasicInteger 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)) {a[j] = a[j] + b[j] * a[j + (1 << i)];b[j] = b[j] * b[j + (1 << i)];}}cout << a[0] + 1 << endl;return 0;}