#265725 (C++14) No.696 square1001 and Permutation 5

• 問題: No.696 square1001 and Permutation 5
• ユーザー: yuppe19 😺
• 提出日時: 2018-06-15 18:03:04
• 言語: C++14 (gcc 13.2.0 + boost 1.83.0)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 11,839 bytes
• コンパイル時間: 294 ms
• コンパイル使用メモリ: 50,988 KB
• 最終ジャッジ日時: 2023-09-13 04:39:35
• 合計ジャッジ時間: 723 ms
• ジャッジサーバーID （参考情報）: judge13 / judge15

コンパイルメッセージ

main.cpp:100:16: エラー: ‘string’ does not name a type
  100 |   bigint(const string val);
      |                ^~~~~~
main.cpp:143:22: エラー: ‘string’ does not name a type
  143 | bigint::bigint(const string s) {
      |                      ^~~~~~
main.cpp: コンストラクタ ‘bigint::bigint(int)’ 内:
main.cpp:144:12: エラー: invalid types ‘const int[int]’ for array subscript
  144 |   minus = s[0] == '-';
      |            ^
main.cpp:145:20: エラー: request for member ‘size’ in ‘s’, which is of non-class type ‘const int’
  145 |   int last = int(s.size());
      |                    ^~~~
main.cpp:151:27: エラー: invalid types ‘const int[int]’ for array subscript
  151 |       v[k] = v[k] * 10 + s[j] - '0';
      |                           ^
main.cpp: コンストラクタ ‘bigint::bigint(i64)’ 内:
main.cpp:163:14: エラー: ‘::abs’ has not been declared
  163 |     v[i] = ::abs(int(y % BASE));
      |              ^~~
main.cpp: メンバ関数 ‘void bigint::print() const’ 内:
main.cpp:364:15: エラー: ‘putchar’ was not declared in this scope; did you mean ‘char’?
  364 |   if(minus) { putchar('-'); }
      |               ^~~~~~~
      |               char
main.cpp:365:3: エラー: ‘printf’ was not declared in this scope
  365 |   printf("%lld", v[n-1]);
      |   ^~~~~~
main.cpp:3:1: 備考: ‘printf’ is defined in header ‘<cstdio>’; did you forget to ‘#include <cstdio>’?
    2 | #include <vector>
  +++ |+#include <cstdio>
    3 | using namespace std;
main.cpp: メンバ関数 ‘void bigint::println() const’ 内:
main.cpp:373:3: エラー: ‘putchar’ was not declared in this scope; did you mean ‘char’?
  373 |   putchar('\n');
      |   ^~~~~~~
      |   char
main.cpp: 関数 ‘int main()’ 内:
main.cpp:432:10: エラー: ‘scanf’ was not declared in this scope
  432 |   int n; scanf("%d", &n);
      |          ^~~~~

ソースコード

#include <tuple>
#include <vector>
using namespace std;
using i64 = long long;

// {{{ mod_mul, extgcd, mod_inv, mod_pow
inline i64 mod_mul(const i64& x, const i64& y, const i64& m) {
  // yとmの最大ビット長はともに48ビット。
  // http://codeforces.com/blog/entry/15884
  // 12 < floor(63 - log2(MAX_VALUE)) = 15
  // 0xfff = (1<<12) - 1
  i64 b, res = y * (x & 0xfff);
  res += (b=(y<<12) % m) * ((x>>12) & 0xfff);
  res += (b=(b<<12) % m) * ((x>>24) & 0xfff);
  res += (b<<12) % m     * ((x>>36) & 0xfff);
  res %= m;
  return res;
}

inline tuple<i64, i64, i64> extgcd(const i64& x, const i64& y) {
  if(y == 0) { return make_tuple(1LL, 0LL, x); }
  i64 a, b, d; tie(a, b, d) = extgcd(y, x%y);
  return make_tuple(b, a-x/y*b, d);
}

inline i64 mod_inv(const i64 a, const i64 m) {
  i64 x, _, d; tie(x, _, d) = extgcd(a, m);
  return (x % m + m) % m;
}

inline i64 mod_pow(const i64& a, const i64& r, const i64& n, const i64& m) {
  if(n == 0) { return r; }
  if(n & 1)  { return mod_pow(a, mod_mul(a, r, m), n-1, m); }
  return mod_pow(mod_mul(a, a, m), r, n>>1, m);
}

inline i64 mod_pow(const i64 a, const i64 n, const i64 m) {
  return mod_pow(a, 1, n, m);
}
// }}}

struct FMT {
  static void fmt(const int, vector<i64>&);
  static void ifmt(const int, vector<i64>&);
  static void convol(const int, vector<i64>&, vector<i64>&);
private:
  static constexpr i64 N = 5LL << 37;
  static constexpr i64 O = 2003LL;
  static constexpr i64 M = N * 211 + 1;
  static void myfmt(const int, vector<i64>&, const bool);
};

// {{{ FMT 実装
void FMT::myfmt(const int logn, vector<i64> &a, const bool inv) {
  const int n = 1 << logn;
  for(int H=1, W=n>>1; H<n; H<<=1, W>>=1) {
    vector<i64> y = a;
    i64 r = mod_pow(O, N/(H*2), M);
    if(inv) { r = mod_inv(r, M); }
    i64 w = 1;
    for(int k=0; k<H; ++k) {
      for(int j=0; j<W; ++j) {
        i64 y0 = y[2*W*k+j],
            y1 = mod_mul(y[2*W*k+j+W], w, M);
        a[W* k   +j] = y0 + y1 < M ? y0 + y1     : y0 + y1 - M;
        a[W*(k+H)+j] = y0 < y1     ? y0 - y1 + M : y0 - y1;
      }
      w = mod_mul(w, r, M);
    }
  }
}

void FMT::fmt(const int logn, vector<i64> &a) {
  myfmt(logn, a, false);
}

void FMT::ifmt(const int logn, vector<i64> &a) {
  myfmt(logn, a, true);
  int n = 1 << logn;
  i64 inv = mod_inv(n, M);
  for(int i=0; i<n; ++i) {
    a[i] = mod_mul(a[i], inv, M);
  }
}

void FMT::convol(const int logn, vector<i64> &a, vector<i64> &b) {
  fmt(logn, a);
  fmt(logn, b);
  for(int i=0; i<1<<logn; ++i) {
    a[i] = mod_mul(a[i], b[i], M);
  }
  ifmt(logn, a);
}
// }}}

constexpr int BASE_DIGITS = 4;
constexpr int BASE = 10000;
struct bigint {
  bigint(void);
  bigint(const string val);
  bigint(const i64 val);
  bigint abs();
  bigint& operator = (const bigint&);
  bigint operator + (const bigint&) const;
  friend bigint operator + (const i64&, const bigint&);
  bigint operator - () const;
  bigint operator - (const bigint&) const;
  bigint operator * (const bigint&) const;
  bigint operator * (const i64&) const;
  bigint& operator += (const bigint&);
  bigint& operator -= (const bigint&);
  bigint& operator *= (const bigint&);
  bigint& operator *= (const i64&);
  bool operator <  (bigint&) const;
  bigint pow(const int) const;
  void print() const;
  void println() const;
  friend bigint factorial(const int&);
private:
  int minus;
  int n; // vの要素数
  vector<i64> v;
  static bigint init(const int size);
  inline bool absGreater(const bigint&, const bigint&) const;
  inline bigint absAdd(const bigint&, const bigint&) const;
  inline bigint sub(const bigint&, const bigint&) const;
  inline bigint fftmul(const bigint&, const bigint&) const;
  inline vector<i64> karatsuba(const vector<i64>&, const vector<i64>&) const;
  inline bigint karatsuba(const bigint&, const bigint&) const;
  static bigint pow(const bigint&, const bigint&, const int);
};

// {{{ bigint 実装
bigint::bigint(void) {}

bigint bigint::init(const int size) {
  bigint res;
  res.n = size;
  res.v.assign(size, 0LL);
  return res;
}

bigint::bigint(const string s) {
  minus = s[0] == '-';
  int last = int(s.size());
  int m = last - minus; // 桁数
  n = (m + BASE_DIGITS - 1) / BASE_DIGITS;
  v.assign(n, 0LL);
  for(int i=last-1, k=0; i>=minus; i-=BASE_DIGITS, ++k) {
    for(int j=max(minus, i-BASE_DIGITS+1); j<=i; ++j) {
      v[k] = v[k] * 10 + s[j] - '0';
    }
  }
  if(v[n-1] == 0) { minus = false; } // -0にはしない
}

bigint::bigint(const i64 x) {
  constexpr int N = 5;
  *this = bigint::init(N);
  minus = x < 0;
  i64 y = x;
  for(int i=0; i<N; ++i) {
    v[i] = ::abs(int(y % BASE));
    y /= BASE;
  }
  while(v[n-1] == 0 && n > 1) { --n; }
  v.resize(n);
  if(v[n-1] == 0) { minus = false; } // -0にはしない
}

bigint& bigint::operator = (const bigint &other) {
  minus = other.minus;
  n = other.n;
  v = other.v;
  return *this;
}

bool bigint::absGreater(const bigint& a, const bigint& b) const {
  // abs(a) < abs(b)かどうか。minusフラグを見ずにチェックすればいい。
  if(a.n != b.n) { return a.n < b.n; }
  for(int i=a.n-1; i>=0; --i) {
    if(a.v[i] != b.v[i]) { return a.v[i] < b.v[i]; }
  }
  return false; // abs(a) == abs(b)のときはfalseを返す
}

bool bigint::operator < (bigint& other) const {
  if(minus != other.minus) { return minus; }
  return absGreater(*this, other) ^ minus;
}

bigint bigint::absAdd(const bigint& a, const bigint& b) const {
  // abs(a) + abs(b) を計算する
  int size = max(a.n, b.n) + 1;
  bigint res = bigint::init(size);
  for(int i=0; i<a.n; ++i) { res.v[i] += a.v[i]; }
  for(int i=0; i<b.n; ++i) { res.v[i] += b.v[i]; }
  for(int i=0; i<size; ++i) {
    if(res.v[i] >= BASE) { // 繰り上がり
      ++res.v[i+1];
      res.v[i] -= BASE;
    }
  }
  while(res.v[res.n-1] == 0 && res.n > 1) { --res.n; }
  res.v.resize(res.n);
  return res;
}

bigint bigint::abs() {
  bigint res = *this;
  res.minus = false;
  return res;
}

bigint bigint::sub(const bigint& a, const bigint& b) const {
  // 必ず abs(a) >= abs(b) になるように引数は来る
  // abs(a) - abs(b) を計算する
  int size = max(a.n, b.n) + 1;
  bigint res = bigint::init(size);
  for(int i=0; i<a.n; ++i) { res.v[i] += a.v[i]; }
  for(int i=0; i<b.n; ++i) { res.v[i] -= b.v[i]; }
  for(int i=0; i<size; ++i) {
    if(res.v[i] < 0) { // 借りてくる
      --res.v[i+1];
      res.v[i] += BASE;
    }
  }
  while(res.v[res.n-1] == 0 && res.n > 1) { --res.n; }
  res.v.resize(res.n);
  return res;
}

bigint bigint::operator + (const bigint& other) const {
  bigint res;
  if(minus == other.minus) { // +, + or -, -
    res = absAdd(*this, other);
    res.minus = minus;
  } else if(absGreater(*this, other)) { // +, - or -, +
    res = sub(other, *this);            // sub()を簡単に実装するために、こことelseの部分の二つはまとめない方がいいと思う
    res.minus = other.minus;
  } else {
    res = sub(*this, other);
    res.minus = minus;
  }
  if(res.n == 1 && res.v[0] == 0) { res.minus = false; }
  return res;
}

bigint operator + (const i64& other, const bigint& x) {
  return x + other;
}

bigint bigint::operator - () const {
  bigint obj = *this;
  obj.minus = !minus;
  return obj;
}

bigint bigint::operator - (const bigint& other) const {
  return *this + (-other);
}

bigint bigint::fftmul(const bigint& a, const bigint& b) const {
  int size = max(a.n, b.n) * 2;
  int m; for(m=0; 1<<m < size; ++m) /* nop */ ;
  bigint res = bigint::init(1<<m);
  vector<i64> c(1<<m, 0);
  for(int i=0; i<a.n; ++i) { res.v[i] = a.v[i]; }
  for(int i=0; i<b.n; ++i) { c[i]     = b.v[i]; }
  FMT::convol(m, res.v, c);
  for(int i=0; i<(1<<m)-1; ++i) {
    res.v[i+1] += res.v[i] / BASE;
    res.v[i]   %= BASE;
  }
  while(res.v[res.n-1] == 0 && res.n > 1) { --res.n; }
  res.v.resize(res.n);
  res.minus = a.minus ^ b.minus;
  return res;
}

vector<i64> bigint::karatsuba(const vector<i64>& a, const vector<i64>& b) const {
  int n = int(a.size());
  vector<i64> res(n + n);
  if(n <= 32) {
    for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) res[i+j] += a[i] * b[j];
    return res;
  }
  int k = n >> 1;
  vector<i64> a1(begin(a), begin(a) + k),
              a2(begin(a) + k, end(a)),
              b1(begin(b), begin(b) + k),
              b2(begin(b) + k, end(b)),
              a1b1 = karatsuba(a1, b1),
              a2b2 = karatsuba(a2, b2);
  for(int i=0; i<k; ++i) { a2[i] += a1[i]; b2[i] += b1[i]; }
  vector<i64> r = karatsuba(a2, b2);
  for(int i=0, m=int(a1b1.size()); i<m; ++i) { r[i]     -= a1b1[i]; }
  for(int i=0, m=int(a2b2.size()); i<m; ++i) { r[i]     -= a2b2[i]; }
  for(int i=0, m=int(r.size());    i<m; ++i) { res[i+k] += r[i]; }
  for(int i=0, m=int(a1b1.size()); i<m; ++i) { res[i]   += a1b1[i]; }
  for(int i=0, m=int(a2b2.size()); i<m; ++i) { res[i+n] += a2b2[i]; }
  return res;
}

bigint bigint::karatsuba(const bigint& ba, const bigint& bb) const {
  vector<i64> a(begin(ba.v), end(ba.v)),
              b(begin(bb.v), end(bb.v));
  int size = max(ba.n, bb.n);
  int m; for(m=0 ; 1<<m < size; ++m) /* nop */ ;
  a.resize(1<<m); b.resize(1<<m);
  vector<i64> c = karatsuba(a, b);
  int cn = int(c.size());
  bigint res = bigint::init(cn);
  for(int i=0; i<cn-1; ++i) {
    res.v[i]   += c[i];
    res.v[i+1] += res.v[i] / BASE;
    res.v[i]   %= BASE;
  }
  while(res.v[res.n-1] == 0 && res.n > 1) { --res.n; }
  res.v.resize(res.n);
  res.minus = ba.minus ^ bb.minus;
  return res;
}

bigint bigint::operator * (const bigint& other) const {
  return max(n, other.n) < 1000 ? karatsuba(*this, other) : fftmul(*this, other);
}

bigint bigint::operator * (const i64& other) const {
  return karatsuba(*this, bigint(other));
}

bigint& bigint::operator += (const bigint& other) {
  *this = *this + other;
  return *this;
}

bigint& bigint::operator -= (const bigint& other) {
  *this = *this - other;
  return *this;
}

bigint& bigint::operator *= (const bigint& other) {
  *this = *this * other;
  return *this;
}

bigint& bigint::operator *= (const i64& other) {
  *this = *this * bigint(other);
  return *this;
}

bigint bigint::pow(const bigint &x, const bigint &r, const int n) {
  if(n == 0) { return r; }
  if(n & 1)  { return pow(x, r*x, n-1); }
  return pow(x*x, r, n>>1);
}

bigint bigint::pow(const int n) const {
  return bigint::pow(*this, 1, n);
}

void bigint::print() const {
  if(minus) { putchar('-'); }
  printf("%lld", v[n-1]);
  for(int i=n-2; i>=0; --i) {
    printf("%04lld", v[i]);
  }
}

void bigint::println() const {
  print();
  putchar('\n');
}

inline bigint recfact(const int start, const int n) {
  if(n <= 2) {
    bigint r = bigint(start);
    for(int i=start+1; i<start+n; ++i) { r *= bigint(i); }
    return r;
  }
  int i = n / 2;
  return recfact(start, i) * recfact(start+i, n-i);
}

inline bigint factorial(const int n) {
  return recfact(1, n);
}
// }}}

template <class T>
struct BIT {
  int N;
  vector<T> data;
  BIT(int n);
  T sum(int k);
  void add(int k, T x);
};

// {{{ BIT 実装
template <class T>
BIT<T>::BIT(int n) {
  N = n + 1;
  data.assign(N, 0);
}

template <class T>
T BIT<T>::sum(int k) {
  T res = 0;
  for(++k; k>0; k-=k&-k) { res += data[k]; }
  return res;
}

template <class T>
void BIT<T>::add(int k, T x) {
  for(++k; k<N; k+=k&-k) { data[k] += x; }
}
// }}}

vector<i64> v;

pair<bigint, bigint> f(int lo, int hi) {
  if(hi - lo == 1) { return {v[lo], lo+1}; }
  int md = (lo + hi) / 2;
  bigint x0, x1, y0, y1;
  tie(x0, x1) = f(lo, md);
  tie(y0, y1) = f(md, hi);
  return {y0*x1+x0, x1*y1};
}

int main(void) {
  int n; scanf("%d", &n);
  vector<int> a(n);
  v.resize(n);
  BIT<i64> bit(n+1);
  for(int i=0; i<n; ++i) {
    scanf("%d", &a[i]);
    bit.add(--a[i], 1);
  }
  for(int i=0; i<n; ++i) {
    v[n-i-1] += bit.sum(a[i] - 1);
    bit.add(a[i], -1);
  }
  bigint res = f(0, n).first + 1;
  res.println();
  return 0;
}