結果

問題 No.696 square1001 and Permutation 5
ユーザー square1001square1001
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

// +----------------------------------
// | 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 <= 4
static 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); // large
BasicInteger b4(b1 < b2 ? b1 : b2); // small
int 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 <= 8192
const 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0